Hide

Dynamic Programming: Coin Change

In this task, you will write a problem that solves the following computational problem. See the lab instructions for further details.

You are trying to buy a book which costs $n$ copper, and at your disposal you have a large number of copper , silver, gold and platinum coins. Each silver coin is worth some integer number $a$ of copper coins, each gold coin is worth some integer number $b$ of copper coins, and each platinum coin is worth some integer number $c$ of copper coins.

You could simply dish up $n$ copper coins, but this is a lot of coins and the transaction would be smoother if you used a few silver/gold/platinum coins in order to reduce the total number of coins used. Assuming you have more than $n$ coins of each type, what is the minimum number of coins do you need to produce an amount worth exactly $n$ copper?

For example, if silver is worth 10 copper, gold is worth 100 copper, and platinum is worth 1000 copper, then the amount 4711 could be produced with 4 platinum coins, 7 gold coins, 1 silver coin, and 1 copper coin, for a total of 13 coins.

Input

The input consists of four integers, each on a separate line:

  • The integer $n$, the amount in copper you are trying to produce.

  • The integer $a$, the value in copper of a silver coin.

  • The integer $b$, the value in copper of a gold coin.

  • The integer $c$, the value in copper of a platinum coin.

Output

Output the minimum number of coins needed to produce an amount worth exactly $n$ copper.

Sample Input 1 Sample Output 1
10
2
3
4
3
Sample Input 2 Sample Output 2
10
5
6
7
2
Sample Input 3 Sample Output 3
0
10
100
1000
0
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
Source KTH EECS Algorithms & Complexity
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in