This question is a repeat of Quest 4 from Round 3 in the 2008/2009 season of DWITE. Tony's flights got rescheduled to a red-eye for the following day, totally messing with his planned work schedule.

In an attempt to make the jobs of cashiers easier (and more accurate!),
lets write a tool that will figure out the least amount of coins
necessary to dispense the *exact* change.

The caveat is that the tool needs to be *dynamic*, and be able to work with foreign currencies.

The input file **DATA4.txt**
will contain 5 sets of input. The first line of the set will be the
amount needed to be dispensed, an integer 1 <= m <= 100. The
second line of the set will be the number of coin types, an integer 1
<= n <= 10. Followed by n lines of coin values, each a unique
integer 1 <= c <= 100.

The output file **OUT4.txt** will contain 5 integers, the minimum number of coins required to make *exact* change for each input set.

*Note:* being *greedy* will give part marks. A *dynamic* solution is required to pass all 5 test cases.

*Explanation of sample input; second set*:
There are three coin types: 25, 10, and 4 (note that input is not
necessary in descending order). It's possible to put together an exact
change for 37 in 4 coins -- 25 + 4 + 4 + 4 = 37

66 4 25 10 5 1 37 3 10 25 4

5 4