Andrew and the Meatballs
Andrew likes meatballs very much.
He has N plates of meatballs, here the ith plate contains Pi meatballs. You need to find the minimal number of plates Andrew needs to take to his trip to Las Vegas, if he wants to eat there at least M meatballs. Note that each plate is already packed, i.e. he cannot change the amount of meatballs on any plate.
The first line of the input contains an 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 M. The second line contains N space-separated integers P1, P2, ..., PN.
For each test case, output an integer, denoting the minimum number of plates. If it's impossible to take at least M meatballs, print -1.
- 1 ≤ T ≤ 7777
- 1 ≤ N ≤ 7
- 1 ≤ M, Pi ≤ 1018
Input: 1 4 7 1 2 3 4 Output: 2
If he takes 3rd and 4th plates, then we may eat P3 + P4 = 7 meatballs in Las Vegas. This is the only way for eating at least M = 7 meatballs with 2 plates.
|Tags||ad-hoc, cakewalk, cook33, sorting, witua|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.