Making Change

Poor Bessie has taken a job at the convenience store just across the border in Slobbovia. Slobbovians use a different currency than the USA, and the values of their coins change from day to day!

Help Bessie give shoppers optimal change, that is, change using the fewest possible coins. She must make exactly $C$ cents of change ($1 \le C \le 1000$) using $N$ distinct coin denominations ($1 \le N \le 10$). She may use any number of coins of each denomination, and every input can always be made exactly with the given coins.

For example, if the available denominations are 50, 25, 10, 5, and 1, then 93 cents can be made with the fewest coins as one 50, one 25, one 10, one 5, and three 1s, for a total of 7 coins.

• Line 1: Two space-separated integers, $C$ and $N$.
• Lines 2 through $N+1$: Each line contains one coin denomination that may be used. All denominations are distinct integers.

• Line 1: A single integer, the minimum number of coins needed to make $C$ cents.