## Let’s get some Bytelandian Gold Coins (;

In Byteland they have a very strange monetary system. Each Bytelandian Gold Coins have 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 Byteland Gold coin.

**Output**

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

**Explanation**

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.

## SAMPLE INPUT

12 2

## SAMPLE OUTPUT

13 2

## Solution With Explanation

From the problem definition, say f (n) = ways to compute the change.

```
f (n) = max (n, f (n / 2) + f (n / 3) + f (n / 4)) (by definition).
f (0) = 0 (Base case).
```

**Problem 1:** Writing a simple recursive solution will time out due to exponential complexity i.e. **O (3 ^{n })**.

**Problem 2:**Writing a linear dynamic programming solution using arrays will exceed memory limit since

**N**can be

**10**in the worst case.

^{9 }To circumvent both of the aforementioned problems, we can use maps and memorization.

**Note:** This is one of those problems where state space is extra large and memoization only explores space what is needed unlike bottom-up dynamic programming which needs one to visit all the state space, memoization is the preferred solution in this case.

**Time Complexity: O (N) Space Complexity: O (log N)**

### Code in C++

```
// {{{ Headers
// vim:filetype=cpp:foldmethod=marker:foldmarker={{{,}}}
#include <cassert>
#include <cctype>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <fstream>
#include <iostream>
#include <sstream>
#include <ext/numeric>
using namespace std;
using namespace __gnu_cxx;
// }}}
typedef long long int64;
const int INF = 0x3f3f3f3f;
template <class T> inline int len (const T &a) { return a.size (); }
#define MAXN 50
char line [MAXN];
map <int, int64> memo;
int64
solve (int n) {
if (n == 0 || n == 1) return n;
if (memo.count (n)) return memo [n];
int64 ret = n;
ret = max (ret, solve (n / 2) + solve (n / 3) + solve (n / 4));
return memo [n] = ret;
}
int
main () {
#ifdef LOCALHOST
freopen ("test.in", "r", stdin);
// freopen ("test.out", "w", stdout);
#endif
int N;
while (fgets (line, MAXN, stdin)) {
sscanf (line, "%d", &N);
int64 ret = solve (N);
printf ("%lld\n", ret);
}
return 0;
}
```