Chef and Fixed Deposits solution codechef

For Solution

Click Here!

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 $i^{t h}$ of which is worth $A_{i}$ 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.

Input Format

The first line of input contains a single integer $T$ , denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers — $N$ and $X$ , as described in the statement.
The second line of each test case contains $N$ space-separated integers — the $i^{t h}$ of which is $A_{i}$ .

Output Format

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

Constraints

$1 \leq T, A_{i}, N \leq 100$
$1 \leq X \leq 10^{4}$

Subtasks

Subtask #1 (100 points): Original constraints

Sample Input 1

Sample Output 1

Explanation

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

Test case $2$ : No matter which FDs Chef opens, he cannot have $\geq 15$ coins, so the answer is $- 1$ .

For Solution

Click Here!