Greedy Algorithms

Greedy algorithms are a popular set of approaches that build the final solution piece-by-piece always choosing the most obvious/optimal solution at each stage. They are usually pretty straightforward but sometimes might be tricky to figure out the heuristic at each step.

Challenge

You have a knapsack and n items. You would like to fit as many items as possible but you know that the knapsack will tear apart if the items in it are too heavy (if the total weight exceeds the threshold t). You’d like to know the maximum number of items you can put in your bag so that it’s okay to carry it.

Input

The first line of the input contains two integers n (1 ≀ n ≀ ) and t (1 ≀ t ≀ ) - the number of items and the maximum threshold the knapsack can carry.
The next line contains n space-separated integers (1 ≀ ≀ ) - the weights of each of the items.

Output

The program should print the maximum number of items you can carry.

Examples

Input
Output
7 10 4 1 2 5 8 7 1
4

Explanation

We can carry 1, 2, 5, 1, or 4, 1, 2, 1, or 1, 2, 7, 1. For all of the cases there are 4 items in total.
Β 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue