Given k coin denominations (unlimited supply of each) and an amount, find the minimum number of coins whose values add up exactly to the amount, or report that it is impossible. Greedy "largest coin first" is not correct in general (coins {1, 3, 4}, amount 6), so use bottom-up dynamic programming: dp[x] = fewest coins for amount x.
Input. The first line holds k (1 ≤ k ≤ 50). The second line holds the k distinct positive coin values (each ≤ 10 000). The third line holds the amount (0 ≤ amount ≤ 100 000).
Output. One line:
Minimum coins: X
where X is the minimum count, 0 for amount 0, or -1 if the amount cannot be made.
Example.
Input:
3
1 3 4
6
Output:
Minimum coins: 2