Gold
Coins
In Byteland, they have a very strange monetary system.
Each
Bytelandian gold coin has an integer number written on it. A coin N
can be exchanged in a bank into three coins: N/2, N/3 and N/4. However, these
numbers are all rounded down (the banks have to make a profit).
You
can also sell Bytelandian coins for American dollars. The exchange rate is 1:1.
However, you cannot buy Bytelandian coins.
You
have one gold coin. What is the maximum amount of American dollars you can get
for it?
Input:
The input will contain single line
with a number N, 0 <= N <= 1 000 000 000. It is the number written on
your coin.
Output:
The maximum amount of American
dollars you can make.
|
Sample Input1:
|
Sample Input2:
|
Sample Input3:
|
|
12
|
2
|
120
|
|
Sample Output1:
|
Sample Output2:
|
Sample Output3:
|
|
13
|
2
|
144
|
Explanations:
You can change 12
into 6, 4 and 3, and then change these into $6+$4+$3 = $13.
If you try
changing the coin 2 into 3 smaller coins, you will get 1, 0 and 0, and later
you can get no more than $1 out of them. It is better just to change the 2 coin
directly into $2.
Для отправки решений необходимо