##### DWITE Online Computer Programming Contest, April 2010, Problem 4

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!), 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 will contain 5 sets of input. The first line of the set will be the amount needed to be dispensed, an integer . The second line of the set will be the number of coin types, an integer . Followed by lines of coin values, each a unique integer .

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

*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 — .

#### Sample Input

```
66
4
25
10
5
1
37
3
10
25
4
```

#### Sample Output

```
5
4
```

Problem Resource: DWITE

## Comments

It's exactly the same question as dwite08c3p4 but the problem type of that one is Brute Force and this one is Dynamic Programming.

Well now they're both Dynamic Programming