## COINS - Bytelandian 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. But 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. But you can not 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 several test cases (not more than 10). Each testcase is a single line with a number n, 0 <= n <= 1 000 000 000. It is the number written on your coin.

### Output

For each test case output a single line, containing the maximum amount of American dollars you can make.

### Example

```Input:
12
2

Output:
13
2
```

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.

hide comments
 upsehu: 2021-05-15 09:09:27 @selectaman take input each time and check with the length of the input, if it is zero than stop else continue till 10 karthik_spoj1: 2021-01-26 13:28:44 be careful while taking inputs while(cin>>n){} -- works and arrays + recursion - exceeds memory using map the not 1000 000 000 memory is created it depends on the testcases> so map works - but is not the optimal way all the time. aashish0909: 2021-01-21 14:13:38 @deep_97 Your array is exceeding the memory limit deep_97: 2021-01-19 18:09:31 Why is map working to store the data and not arrays? When I am using arrays to store the data, it is giving SIGKILL but for map it's running smoothly? princemishra: 2021-01-09 14:29:13 just use recursion + map in cpp dhruv_sh: 2021-01-07 07:03:11 AC on the second attempt. Be careful while taking input. while(cin>>n){.....} <- this helped saikumarpatel: 2021-01-05 11:47:44 help me where is my mistake? [NG]: Read the footer. Last edit: 2021-01-05 22:20:33 tejasreddyk: 2021-01-05 11:46:51 It was little confusing 1 gold coin = 1 \$, I considered any gold coin to be worth 1\$.... apparently it was a 2\$ if it was labeled 2 on it nitish_verma26: 2020-12-11 17:56:02 Use long long. I found it interesting that for numbers less than 12, max value will be that number itself. Recursion + Map to memoize seems like the way to go. monkeyboy9996: 2020-12-07 18:22:20 Can be done via recursion too!!!

 Added by: Tomek Czajka Date: 2005-05-03 Time limit: 9s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: NODEJS PERL6 VB.NET Resource: Purdue Programming Contest Training