Coin Change

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 16M

Author:
Problem type

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 Specification

Line 1: x, an integer between 1 and 10\,000.
Line 2: n, the number of different denominations.
Line 3 \ldots 3+n: the denominations of the coins.

Output Specification

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

Sample Input

24
4
12
13
5
6

Sample Output

2

Comments

There are no comments at the moment.