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.

10
2
3
4

3

10
5
6
7

2

0
10
100
1000

0