Quin inherited the archive at the cliffside roost of Stormrest along with its curious bookkeeping system for vaults. Time to make sense of it. Task: Coins of n given sizes may be used without limit. Print the minimum number of coins summing exactly to amount, or -1. Input format: First line: amount and n. Second line: n distinct coin sizes. Output format: Print the minimum coin count, or -1. Constraints: 0 <= amount <= 4000; 1 <= n <= 50; 1 <= coin <= 10^4.
Example 1:
Example 2:
Example 3:
Constraints:
0 <= amount <= 4000; 1 <= n <= 50; 1 <= coin <= 10^4.
