Stay Healthy!

2.5

4 votes
Basics of Greedy Algorithms, Greedy Algorithms, Algorithms
Problem

You have N pills of characteristic values a1,a2,...,an.

On each day i you can take the ith pill and increase your health by ai points H:=H+ai or Do nothing and take 1 point of damage H:=H1 , where H is a value deenoting your health. You die if your health becomes zero. Initially H=V (where V is a value given in the input).

What is the minimum number of pills you should take to survive for N days.

Input 

Each test consists of multiple test cases. The first line contains a single integer t  ( 1t104 ) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers N and V where 1N,V200000

The second line of each test case contains N space seperated integers a1,a2,...,aN ( 1ai200000)

The sum of N over all test cases does not exceed 200000.

Output

For each test case print the minimum number of pills you should take to survive for N days.

Sample Input
3
5 1
1 1 1 1 1 
5 2
1 3 1 1 3 
3 4 
1000 1000 1000   
Sample Output
3
1
0
Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

In the first test case, you must take 1st3rd and 5th pills to survive.

Editor Image

?