Given a value of x cents, and an infinite supply of coins of n denominations, followed by their denominations, find the least amount of coins required to make change for x.

Input

Line 1: x, an integer between 1 and 10000

Line 2: n, the number of different denominations

Line 3..3+n: the denominations of the coins

Output

An integer, on a single line - the least coins required to make change for x.

Example

Input:
24
4
12
13
5
6

Output:
2

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Apr 08, 2011
Author: jargon

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Guys I am getting WA for just one case i.e 10 making 110/120.Can you please tell me what acutally answer for this case.

You're making a mistake in your end conditions.

Edit: Here's another hint for you: you're going out of bounds.

Why is my Pascal solution faster than my C++ solution? They're practically identical.

For the past few months, running time measurements for programs have been abnormally slow and unpredictable. This is a known issue with the server that we just have to cope with for now. If it ever gets fixed in the future, it's likely that all submissions that were affected will be rejudged for consistency.

It could be possible there is no amount of coins that can make change for x

See my note below.

can the coins added together be bigger than x as long as it is the least number 

You may assume they will be smaller than 100000. (Use a longint).

Did you even read Yves's comment? It will tell you all you need to know.
N is at max 100. A denomination is at most 1000. 100*1000=100000...use a longint.

thx...more

1 <= n <= 100; 1 <= di <= 1000, where di = ith denomination coin.
Also, it will always be possible to make change for x.