Chef and Fixed Deposits solution codechef- Chef wants to make a purchase. For this, he needs X gold coins, but he has none at the moment. Chef has N fixed deposits, the ith of which is worth Ai coins. He wants to open the minimum number of these deposits so that he has at least X coins. You have to tell Chef the minimum number of fixed deposits he must open in order to have X coins, or say that this is impossible.

Chef and Fixed Deposits solution codechef

Chef wants to make a purchase. For this, he needs XX gold coins, but he has none at the moment.

Chef has NN fixed deposits, the ithith of which is worth AiAi coins. He wants to open the minimum number of these deposits so that he has at least XX coins.

You have to tell Chef the minimum number of fixed deposits he must open in order to have XX coins, or say that this is impossible.

Input Format

  • The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains two space-separated integers — NN and XX, as described in the statement.
  • The second line of each test case contains NN space-separated integers — the ithith of which is AiAi.

Output Format

For each test case, output one line containing the answer — the minimum number of FDs Chef must open to have at least XX coins. If it is not possible for him to open FDs such that he has at least XX coins, output 1−1.

Constraints

  • 1T,Ai,N1001≤T,Ai,N≤100
  • 1X1041≤X≤104

Subtasks

Subtask #1 (100 points): Original constraints

Sample Input 1 

4
4 6
4 3 5 1
3 15
1 5 3
2 5
10 3
4 7
1 2 3 4

Sample Output 1 

2
-1
1
2

Explanation

Test case 11: Chef can open the first and second FDs to get 4+3=74+3=7 coins.

Test case 22: No matter which FDs Chef opens, he cannot have 15≥15 coins, so the answer is 1−1.

Leave a Comment

Your email address will not be published.