InternDoor

Pay an amount with the fewest coins

Mediumdynamic programmingRead the input, print the output

Reported in interviews at (where)

A country has coins of n different values, and you have as many of each as you like. For each test, find the fewest coins that add up to exactly amount, or -1 if no set of coins does.

Always taking the biggest coin that fits does not always give the fewest coins.

Input

The first line holds T, the number of tests. Each test is two lines: n and amount, then the n coin values.

Output

For each test, one line: the fewest coins that make its amount, or -1.

Example
Input
4
3 6
1 3 4
1 7
2
2 0
5 9
3 11
1 5 6
Output
2
-1
0
2
  1. Taking the biggest coin first gives 4 + 1 + 1, three coins, but 3 + 3 uses two.
  2. Coins of 2 only make even amounts.
  3. An amount of 0 needs no coins.
  4. 5 + 6.

Limits

  • 1 <= T <= 100
  • 1 <= n <= 50, and the n coin values differ
  • 1 <= each coin value <= 10000
  • 0 <= amount <= 10000
  • n times amount, added over all the tests, is at most 4000000

Hints

Hint 1

Work out the answer for every amount from 0 up: the fewest coins for v is one more than the fewest for v - c, for the best coin c.

Hint 2

Keep a table best[0..amount] with best[0] = 0 and every other amount "impossible" to start; fill it upwards. That is O(n * amount).

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.