## 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.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <iostream>
#include <map>
using namespace std;

long long int get_coins(int N, map<int, long long int> &memoArray);

int main()
{
map<int, long long int> M;
int N;
while (scanf("%lld", &N) != EOF)
{
cout << get_coins(N, M) << endl;
}
return 0;
}
long long int get_coins(int N, map<int, long long int> &memoArray)
{
if (memoArray[N] != 0)
{
return memoArray[N];
}
else
{
if (N >= 0 && N <= 11)
{
memoArray[N] = N;
return N;
}
else
{
return memoArray[N] = get_coins(N / 2, memoArray) + get_coins(N / 3, memoArray) + get_coins(N / 4, memoArray);
}
}
}``````
Copy The Code &

Input

cmd
12
2

Output

cmd
13
2

### #2 Code Example with Java Programming

```Code - Java Programming```

``````//This problem uses a combination of
//topdown and bottom up approach in Dynamic programming
import java.util.Scanner;
class ByteLandian
{
static long[] arr;
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
arr=new long[100000+1];
//calculates the value of maximum dollar  for coin upto 100000
// for coin greater than 100000 it uses recursion
for(int i=1;i<=100000;i++)
{
arr[i]=Math.max((arr[i/2]+arr[i/3]+arr[i/4]),i);
}
while(sc.hasNext())
{
int n=sc.nextInt();
System.out.println(max_dollar(n));
}

}
static long max_dollar(int n)
{
if(n<=100000)
return arr[n];
else
return(max_dollar(n/2)+max_dollar(n/3)+max_dollar(n/4));
}
}``````
Copy The Code &

Input

cmd
12
2

Output

cmd
13
2