Minimum number of coins
Statement
Given a non-negative <<amount>> [[N]] and a <<set of coins>> of [[S]] positive values [[Vi]], return <<the smallest number of coins>> that sum up to the required amount.
NB : You have an unlimited amount of coin of each value at your disposal.
Input description
<<Line 1 :>> A non-negative integer [[N]] for the target amount.
<<Line 2 :>> A non-negative integer [[S]] for the number of possible values coins.
<<S next lines :>> A positive integer [[Vi]] for the value of the i-th coin.
Output description
An integer representing the minimum number of coins that sum up to [[N]], or {{-1}} if the target amount cannot be reached.
Constraints
0 <= [[N]] <= 1e8
0 <= [[S]] <= 50
0 < [[Vi]] <= 500
Game modes
Test cases
Coins only Test
Input
3
2
1 2
Output
2
Do not use your bank notes Validator
Input
4
3
1 5 10
Output
4
Real-life change Test
Input
379
9
1 2 5 10 20 50 100 200 500
Output
7
Validator 2 Validator
Input
899
9
1 2 5 10 20 50 100 200 500
Output
9
How am I supposed to pay ?! Test
Input
152
0
Output
-1
Validator 3 Validator
Input
75
0
Output
-1
What is that money ?! Test
Input
856
24
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Output
10
Validator 4 Validator
Input
1243
24
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Output
13
Let's buy a Castle Test
Input
1527495
9
1 2 5 10 20 50 100 200 500
Output
3060
Validator 5 Validator
Input
1234555
6
1 2 10 50 100 500
Output
2473
Pocket money Test
Input
10
4
1 3 7 8
Output
2
Validator 6 Validator
Input
11
5
1 2 4 7 8
Output
2
Solution language
Solution
Stub generator input