Every season at the lotus ponds of Tranquil Basin, someone must prepare the guildmaster's brief. This year the task falls to Ysolde, armed only with the runs register. 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 <= 10000; 1 <= n <= 50; 1 <= coin <= 10^4.
Example 1:
Example 2:
Example 3:
Constraints:
0 <= amount <= 10000; 1 <= n <= 50; 1 <= coin <= 10^4.
