Making Change

Time limit1sMemory limit128 MB

Summary

Given a target amount and up to 10 coin denominations, find the fewest coins that sum exactly to the target.

Level: Easy3 of 10
Topics: Dynamic programming, Greedy, Array
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples5

Example 1
Input
```
93 5
25
50
10
1
5
```
Expected output
```
7
```
Example 2
Input
```
1 1
1
```
Expected output
```
1
```
Example 3
Input
```
1000 1
1
```
Expected output
```
1000
```
Example 4
Input
```
100 5
1
5
10
25
50
```
Expected output
```
2
```
Example 5
Input
```
6 3
1
3
4
```
Expected output
```
2
```