Problem M
Putovanje
Young Mislav loves spending time in nature and, most of all, he loves spending time in forests. The fresh air and lovely sounds make the forest his favourite location. Mislav has decided to spend this afternoon in a forest and, because he’s so practical, he’s also decided to stuff himself with food. His belly can contain $C$ amount of food.
He will have the opportunity to eat various fruits of nature (mushrooms, chestnuts, berries, and so on) while walking through the forest. All fruits are mutually different given their type and he’d like to eat as much different fruits as possible, but with the condition that he doesn’t overeat. In other words, the total weight of the fruits he’s eaten must not be larger than $C$. Also, when Mislav decides to start eating, he tries to eat every next fruit if it’s possible to eat it and not overeat. In the case when he doesn’t have the capacity to eat it, he just moves on.
An array of weights of $N$ fruits represents the weight and order of fruits that Mislav came across in the forest. Determine the maximum amount of different fruits that Mislav can eat.
Input
The first line of input contains two integers $N$ and $C$ ($1 \leq N \leq 1\, 000$, $1 \leq C \leq 1\, 000\, 000$) from the task. The second line contains $N$ integers $w_ i$ ($1 \leq w_ i \leq 1\, 000$) that represent the fruits’ weight.
Output
The first and only line of output must contain the maximum possible amount of different fruits that Mislav can eat.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 5 3 1 2 1 1 |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
7 5 1 5 4 3 2 1 1 |
3 |
| Sample Input 3 | Sample Output 3 |
|---|---|
5 10 3 2 5 4 3 |
3 |