1325 -- Making Change
Time Limit :1000 MS Memory Limit :65536 KB
Accepts : 47 Submits : 99
User Accepts : 39 User Submits : 43
<Submit>   <Statistics>   <Discuss>

Description

Poor Bessie has taken a job in the convenience store located just over the border in Slobbovia. Slobbovians use different coinages than the USA; their coin values change day-by-day!
 
Help Bessie make optimal change for Slobbovian shoppers. You will need to create C (1 <= C <= 1000) cents of change using N (1 <= N <= 10) coins of various values. All test cases will be solvable using the supplied coins. If 5 coins of values 50, 25, 10, 5, and 1 were available, Bessie would make optimum change (minimal coins) of 93 cents by using 1 x 50, 1 x 25, 1 x 10, 1 x 5, and 3 x 1 coins (a total of 7 coins).
 
How hard could it be? The final two test cases will be challenging.

Input

* Line 1: Two space-separate integers: C and N

* Lines 2..N+1: Each line contains a single unique integer that is a coin value that can be used to create change

Output

* Line 1: A single integer that is the minimum number of coins to create C cents

Sample Input

93 5
25
50
10
1
5

Sample Output

7

 

<Submit>   <Statistics>   <Discuss>
 


Powered by Zhang Zhaoning PDL College of Computer
Since 2006.03.09 | 2007.11.22 | 2010.03.02 Copyright (r) 2006 - 2010 All Rights Reserved