Deep in the moonlit lagoon of Selene, Lothar studies rows of vaults entries. One clean number will settle the guild's oldest argument. 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.
