Contents
Chef and Fixed Deposits solution codechef

For Solution
Click Here!
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 spaceseparated integers — NN and XX, as described in the statement.
 The second line of each test case contains NN spaceseparated 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
 1≤T,Ai,N≤1001≤T,Ai,N≤100
 1≤X≤1041≤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.

For Solution
Click Here!