Time Limit: Java: 2000 ms / Others: 2000 ms
Memory Limit: Java: 65536 KB / Others: 65536 KB
Recently, Dearboy buys a dart for his dormitory, but neither Dearboy nor his roommate knows how to play it. So they decide to make a new rule in the dormitory, which goes as follows:
Given a number N, the person whose scores accumulate exactly to N by the fewest times wins the game.
Notice once the scores accumulate to more than N, one loses the game.
Now they want to know the fewest times to get the score N.
So the task is :
Given all possible dart scores that a player can get one time and N, you are required to calculate the fewest times to get the exact score N.
Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 50) which is the number of test cases. And it will be followed by T consecutive test cases.
Each test case begins with two positive integers M(the number of all possible dart scores that a player can get one time) and N. Then the following M integers are the exact possible scores in the next line.
Notice: M (0 < M < 100), N (1 < N <= 1000000000), every possible score is (0, 100).
For each test case, print out an integer
representing the fewest times to get the exact score N.
If the score can't be reached, just print -1 in a line.
3 3 6 1 2 3 3 12 5 1 4 1 3 2
2 3 -1