8572: DPL_1_A : Coin Changing Problem
[Creator : ]
Description
Find the minimum number of coins to make change for $n$ cents using coins of denominations $d_1, d_2,.., d_m$. The coins can be used any number of times.
Input
$n\ m$
$d_1\ d_2\ ...\ d_m$
Two integers $n$ and $m$ are given in the first line.
The available denominations are given in the second line.
$d_1\ d_2\ ...\ d_m$
Two integers $n$ and $m$ are given in the first line.
The available denominations are given in the second line.
Output
Print the minimum number of coins in a line.
Constraints
$1 ≤ n ≤ 50,000$
$1 ≤ m ≤ 20$
$1 ≤$ denomination $≤ 10,000$
The denominations are all different and contain $1$.
$1 ≤ m ≤ 20$
$1 ≤$ denomination $≤ 10,000$
The denominations are all different and contain $1$.
Sample 1 Input
55 4
1 5 10 50
Sample 1 Output
2
Sample 2 Input
15 6
1 2 7 8 12 50
Sample 2 Output
2
Sample 3 Input
65 6
1 2 7 8 12 50
Sample 3 Output
3