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

In an attempt to make the jobs of cashiers easier (and more accurate!), let’s 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. This is 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 the input set.

*Note:* Being *greedy* will only 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 necessarily 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
```