## Coin Change## Problem code: CCHANGE |

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 6Output: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)

competitivecoderon Oct 09, 2015 - 1:46:27 pm UTC Help me with test case 10jargonon Oct 10, 2015 - 8:08:37 pm UTC Re: Help me with test case 10Edit: Here's another hint for you: you're going out of bounds.

helios26on Mar 14, 2014 - 3:38:20 pm UTCAlexon Mar 14, 2014 - 7:25:02 pm UTC Re: ...michael137on May 19, 2012 - 5:07:15 am UTC outputjargonon May 19, 2012 - 1:54:44 pm UTC Re: outputbobbyg212009on Apr 18, 2011 - 1:02:46 am UTC can the coins added together be bigger than x as long as it is the least numberilovepion Apr 18, 2011 - 1:07:08 am UTC Re: can the coins added together be bigger than x as long as it is the least numDid 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.

bobbyg212009on Apr 20, 2011 - 2:58:28 am UTC Re: Re: can the coins added together be bigger than x as long as it is the leastjargonon Apr 08, 2011 - 8:25:33 pm UTC NoteAlso, it will always be possible to make change for x.