You have unlimited coins of n different values. Print the fewest coins that add up exactly to the amount, or -1 if it is impossible. (Amount 0 needs 0 coins.)
Constraints
- 1 ≤ n ≤ 100
- 1 ≤ coin ≤ 10000
- 0 ≤ amount ≤ 10000
Input and output
- Input
- Line 1: n amount Line 2: n coin values
- Output
- One integer.
Examples
Input 1
3 11
1 2 5Output
35+5+1
Input 2
1 3
2Output
-1Impossible.
Show hints
- Greedy (largest coin first) fails for coins like 1, 3, 4 and amount 6.
- best[x] = 1 + min(best[x − c]).
Show the explanation
Let best[x] be the fewest coins for amount x, with best[0] = 0 and the rest "infinity". For x from 1 to amount and every coin c ≤ x: best[x] = min(best[x], best[x − c] + 1). The answer is best[amount], or -1 if it stayed infinite. O(amount × n) time, O(amount) space.
Original UniCircle question. Last reviewed 21 Oct 2026.