## 原CodeForces–1013AAPilesWithStones

There is a beautiful garden of stones in Innopolis.

Its most beautiful place is the nn piles with stones numbered from 11 to nn.

EJOI participants have visited this place twice.

When they first visited it, the number of stones in piles was x1,x2,…,xnx1,x2,…,xn, correspondingly. One of the participants wrote down this sequence in a notebook.

They visited it again the following day, and the number of stones in piles was equal to y1,y2,…,yny1,y2,…,yn. One of the participants also wrote it down in a notebook.

It is well known that every member of the EJOI jury during the night either sits in the room 108108 or comes to the place with stones. Each jury member who comes there either takes one stone for himself or moves one stone from one pile to another. We can assume that there is an unlimited number of jury members. No one except the jury goes to the place with stones at night.

Participants want to know whether their notes can be correct or they are sure to have made a mistake.

Input

The first line of the input file contains a single integer nn, the number of piles with stones in the garden (1≤n≤501≤n≤50).

The second line contains nn integers separated by spaces x1,x2,…,xnx1,x2,…,xn, the number of stones in piles recorded in the notebook when the participants came to the place with stones for the first time (0≤xi≤10000≤xi≤1000).

The third line contains nn integers separated by spaces y1,y2,…,yny1,y2,…,yn, the number of stones in piles recorded in the notebook when the participants came to the place with stones for the second time (0≤yi≤10000≤yi≤1000).

Output

If the records can be consistent output “Yes”, otherwise output “No” (quotes for clarity).

Examples

input

Copy

5
1 2 3 4 5
2 1 4 3 5


output

Copy

Yes


input

Copy

5
1 1 1 1 1
1 0 1 0 1


output

Copy

Yes


input

Copy

3
2 3 9
1 7 9


output

Copy

No


Note

In the first example, the following could have happened during the night: one of the jury members moved one stone from the second pile to the first pile, and the other jury member moved one stone from the fourth pile to the third pile.

In the second example, the jury took stones from the second and fourth piles.

It can be proved that it is impossible for the jury members to move and took stones to convert the first array into the second array.

#include<iostream>
using namespace std;
int main()
{
int n;
while(cin>>n)
{
int sum1=0,sum2=0;
int a;
for(int i=0;i<n;i++){
cin>>a;
sum1=sum1+a;
}
for(int i=0;i<n;i++){
cin>>a;
sum2=sum2+a;
}
if(sum2<=sum1)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}

## 原CodeForces–1011BPlanningTheExpedit

Natasha is planning an expedition to Mars for nn people. One of the important tasks is to provide food for each participant.

The warehouse has mm daily food packages. Each package has some food type aiai.

Each participant must eat exactly one food package each day. Due to extreme loads, each participant must eat the same food type throughout the expedition. Different participants may eat different (or the same) types of food.

Formally, for each participant jj Natasha should select his food type bjbj and each day jj-th participant will eat one food package of type bjbj. The values bjbj for different participants may be different.

What is the maximum possible number of days the expedition can last, following the requirements above?

Input

The first line contains two integers nn and mm (1≤n≤1001≤n≤100, 1≤m≤1001≤m≤100) — the number of the expedition participants and the number of the daily food packages available.

The second line contains sequence of integers a1,a2,…,ama1,a2,…,am (1≤ai≤1001≤ai≤100), where aiai is the type of ii-th food package.

Output

Print the single integer — the number of days the expedition can last. If it is not possible to plan the expedition for even one day, print 0.

Examples

input

Copy

4 10
1 5 2 1 1 1 2 5 7 2


output

Copy

2


input

Copy

100 1
1


output

Copy

0


input

Copy

2 5
5 4 3 2 1


output

Copy

1


input

Copy

3 9
42 42 42 42 42 42 42 42 42


output

Copy

3


Note

In the first example, Natasha can assign type 11 food to the first participant, the same type 11 to the second, type 55 to the third and type 22 to the fourth. In this case, the expedition can last for 22 days, since each participant can get two food packages of his food type (there will be used 44 packages of type 11, two packages of type 22 and two packages of type 55).

In the second example, there are 100100 participants and only 11 food package. In this case, the expedition can’t last even 11 day.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 105;
int vis[N];  //每种食物的数量
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
int x;
scanf("%d",&x);
vis[x]++;
}
int ans=0;
for(int i=1;i<=m;i++){ //假设可以吃i天
int cnt=0; //如果吃i天，可以供多少人吃
for(int j=1;j<=100;j++)
cnt+=vis[j]/i;
if(cnt>=n) ans=max(ans,i);
}
printf("%d\n",ans);
return 0;
}

## 原CodeForces–1011AAStages

Natasha is going to fly to Mars. She needs to build a rocket, which consists of several stages in some order. Each of the stages is defined by a lowercase Latin letter. This way, the rocket can be described by the string — concatenation of letters, which correspond to the stages.

There are nn stages available. The rocket must contain exactly kk of them. Stages in the rocket should be ordered by their weight. So, after the stage with some letter can go only stage with a letter, which is at least two positions after in the alphabet (skipping one letter in between, or even more). For example, after letter ‘c’ can’t go letters ‘a’, ‘b’, ‘c’ and ‘d’, but can go letters ‘e’, ‘f’, …, ‘z’.

For the rocket to fly as far as possible, its weight should be minimal. The weight of the rocket is equal to the sum of the weights of its stages. The weight of the stage is the number of its letter in the alphabet. For example, the stage ‘a ‘weighs one ton,’ b ‘weighs two tons, and’ z’ — 2626 tons.

Build the rocket with the minimal weight or determine, that it is impossible to build a rocket at all. Each stage can be used at most once.

Input

The first line of input contains two integers — nn and kk (1≤k≤n≤501≤k≤n≤50) – the number of available stages and the number of stages to use in the rocket.

The second line contains string ss, which consists of exactly nn lowercase Latin letters. Each letter defines a new stage, which can be used to build the rocket. Each stage can be used at most once.

Output

Print a single integer — the minimal total weight of the rocket or -1, if it is impossible to build the rocket at all.

Examples

input

Copy

5 3
xyabd


output

Copy

29

input

Copy

7 4
problem


output

Copy

34

input

Copy

2 2
ab


output

Copy

-1

input

Copy

12 1
abaabbaaabbb


output

Copy

1

Note

In the first example, the following rockets satisfy the condition:

• “bdx” (weight is 2+4+24=302+4+24=30);
• “bdy” (weight is 2+4+25=312+4+25=31).

In the second example, target rocket is “belo”. Its weight is 2+5+12+15=342+5+12+15=34.

In the third example, n=k=2n=k=2, so the rocket must have both stages: ‘a’ and ‘b’. This rocket doesn’t satisfy the condition, because these letters are adjacent in the alphabet. Answer is -1.

#include<bits/stdc++.h>
using namespace std;
char s[200];
int main()
{
int n,m;
cin>>n>>m;
getchar();
gets(s);
sort(s,s+n);
int sum=s[0]-'a'+1,k=1;
char ans=s[0];
for(int i=1;i<n;i++)
{
if(k==m) break;
if(s[i]>ans+1)
{
k++;
ans=s[i];
sum=sum+s[i]-'a'+1;
}
}
if(k==m)cout<<sum<<endl;
else cout<<"-1"<<endl;
return 0;
}

## 原SDAU暑假训练第20天DP训练（2018818）

（这是背包九讲看完之后留下的自己觉着挺重要的内容背包九讲

今天进行安全加固改数据库的前缀时的时候不小心把服务器系统弄坏了。。尽力去修了，没弄好，现在用了16号的备份镜像才恢复过来，凭着印象最大的还原的案发前的现场，但是昨天和前天的大概四篇文章还是没了，没有保住。。。

## 原SDAU暑假训练第18天做题（2018816）

HDU一直关着，很烦。做了几个洛谷的题，挑了几个题解发我新博客上了，点击查看