Problem A
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 