Lazy Salesman solution codechef- Ved is a salesman. He needs to earn at least WW rupees in NN days for his livelihood. However, on a given day ii (1≤i≤N1≤i≤N), he can only earn AiAi rupees by working on that day.

Lazy Salesman solution codechef

Ved is a salesman. He needs to earn at least WW rupees in NN days for his livelihood. However, on a given day ii (1iN1≤i≤N), he can only earn AiAi rupees by working on that day.

Ved, being a lazy salesman, wants to take as many holidays as possible. It is known that on a holiday, Ved does not work and thus does not earn anything. Help maximize the number of days on which Ved can take a holiday.

It is guaranteed that Ved can always earn at least WW rupees by working on all days.

Input Format

  • The first line contains a single integer TT – the number of test cases. Then the test cases follow.
  • The first line of each test case contains two integers NN and WW – the size of the array AA and the money Ved has to earn in those NN days.
  • The second line of each test case contains NN space-separated integers A1,A2,,ANA1,A2,…,AN denoting the money which Ved can earn on each day.

Output Format

For each test case, output the maximum number of holidays Ved can take.

Constraints

  • 1T1001≤T≤100
  • 1W100001≤W≤10000
  • 1N1001≤N≤100
  • 1Ai1001≤Ai≤100
  • It is guaranteed that Ved can always earn at least WW rupees by working on all days.

Sample Input 1 

3
5 10
3 2 6 1 3
4 15
3 2 4 6
6 8
9 12 6 5 2 2

Sample Output 1 

2
0
5

Explanation

Test case-1: Ved can work on 22-nd, 33-rd and 55-th day earning 2+6+3=112+6+3=11 rupees W≥W rupees. Thus he can take 22 holidays on the 11-st and the 44-th day.

Test case-2: Ved has to work on all days to earn W≥W rupees. Thus he can not take any holidays.

Test case-3: Ved can work on 22-nd day earning 1212 rupees W≥W rupees. Thus he can take holiday on the remaining days.

For Solution

Click Here!

Leave a Comment

Your email address will not be published.