## Problem Statement

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 test case 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

2Output:

13

2

You can change 12 into 6, 4 and 3, and then change these into 6+6+4+3=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 coin so it is better to exchange 2 coins for 2 dollars.

## Approach to Solution

This problem is a classic example of Recursive Programming. Here the main idea is to get the maximum sum of coins. For cases where **N** > number of coins in (**N/2+N/3+N/3**) we will simply get the change for the exact coin** N**.

# Dictionary to store the number of coins to their corresponding keys array = {0:0,1:1} def solve(n): if n in array: return array[n] #retruns the value of the key if found in array else: array[n] = max(n,solve(n//2)+solve(n//3)+solve(n//4)) return array[n] if __name__ == '__main__': # taking the input i = 10 while(i > 0): n = int(input()) print(solve(n)) i -= 1

Problem link – link

Nice