COCI '15 Contest 6 #2 Putovanje

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

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 \le N \le 1\,000, 1 \le C \le 1\,000\,000) from the task.

The second line contains N integers w_i (1 \le w_i \le 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

5 5
3 1 2 1 1

Sample Output 1

4

Explanation for Sample Output 1

If Mislav decides to start eating from fruit (3), then he will have eaten 3 different fruits (3, 1, 1). If he starts eating from fruit (1), he will have eaten 4 fruits (1, 2, 1, 1).

Sample Input 2

7 5
1 5 4 3 2 1 1

Sample Input 2

3

Sample Input 3

5 10
3 2 5 4 3

Sample Output 3

3

Comments

There are no comments at the moment.