Byteland COINS

While the code below passes

```
z = {}
def fun(n):
if n<=1:
return n
elif n in z:
return z[n]
else:
d = max(n,fun(n/2)+fun(n/3)+fun(n/4))
z[n] = d
return d
import sys
for i in sys.stdin:
print fun(int(i))
```

But code below doesn’t pass both are almost same,

```
# your code goes here
arr = {}
def dp(n):
if n in arr:
return arr[n]
if n==0 or n==1:
arr[n] = n
return n
a = n/3
b = n/2
c = n/4
ans = max(dp(a)+dp(b)+dp(c),n)
arr[n] = ans
return ans
t = input()
for i in xrange(t):
k = input()
print dp(k)
```

Kindly help!