Limak is a little polar bear. He plays by building towers from blocks. Every block is a cube with positive integer length of side. Limak has infinitely many blocks of each side length.

A block with side a has volume a^3. A tower consisting of blocks with sides a_1, a_2, ..., a_{k} has the total volume a_1^3 + a_2^3 + ... + a_{k}^3.

Limak is going to build a tower. First, he asks you to tell him a positive integer X — the required total volume of the tower. Then, Limak adds new blocks greedily, one by one. Each time he adds the biggest block such that the total volume doesn't exceed X.

Limak asks you to choose X not greater than m. Also, he wants to maximize the number of blocks in the tower at the end (however, he still behaves greedily). Secondarily, he wants to maximize X.

Can you help Limak? Find the maximum number of blocks his tower can have and the maximum X ≤ m that results this number of blocks.


-----Input-----

The only line of the input contains one integer m (1 ≤ m ≤ 10^15), meaning that Limak wants you to choose X between 1 and m, inclusive.


-----Output-----

Print two integers — the maximum number of blocks in the tower and the maximum required total volume X, resulting in the maximum number of blocks.


-----Examples-----
Input
48

Output
9 42

Input
6

Output
6 6



-----Note-----

In the first sample test, there will be 9 blocks if you choose X = 23 or X = 42. Limak wants to maximize X secondarily so you should choose 42.

In more detail, after choosing X = 42 the process of building a tower is:  Limak takes a block with side 3 because it's the biggest block with volume not greater than 42. The remaining volume is 42 - 27 = 15.  The second added block has side 2, so the remaining volume is 15 - 8 = 7.  Finally, Limak adds 7 blocks with side 1, one by one. 

So, there are 9 blocks in the tower. The total volume is is 3^3 + 2^3 + 7·1^3 = 27 + 8 + 7 = 42.

Difficulty: competition

Starter code:

Solutions:
im = int(input())

best_steps = 0
best_length = 0

def rec(m, steps, substracted):
    nonlocal best_steps, best_length 
    if m == 0:
        if steps > best_steps:
            best_steps = steps
            best_length = substracted
        elif steps == best_steps:
            best_length = max(best_length, substracted)
        return

    a = 1
    while (a + 1)**3 <= m:
        a += 1

    rec(m - a**3, steps + 1, substracted + a**3)

    if a - 1 != 0:
        rec(a**3-1-(a-1)**3, steps + 1, substracted + (a-1)**3)

rec(im, 0, 0)
print(best_steps, best_length)

from sys import *
setrecursionlimit(1000000)
#d={}
def c(n):
#    t=d.get(n,(0,0))
#    if t!=(0,0): return t
    if n<8: return n,n
    t1=int(n**(1/3)+0.00000000001)
    t2=t1-1
    v1=c(n-t1*t1*t1)
    v1=v1[0]+1,v1[1]+t1*t1*t1
    v2=c(t1*t1*t1-1-t2*t2*t2)
    v2=v2[0]+1,v2[1]+t2*t2*t2
    if v2>v1: v1=v2
#    d[n]=v1
    return v1
    
print(' '.join(map(str,c(int(input())))))

def main():
    def f(n):
        if n < 8:
            return [n, n]
        a = int((n + .5) ** 0.3333333333333333)
        r1 = f(n - a * a * a)
        r1[1] += a * a * a
        a -= 1
        r2 = f(3 * a * (a + 1))
        r2[1] += a * a * a
        if r1 < r2:
            r1 = r2
        r1[0] += 1
        return r1

    print(*f(int(input())))


def __starting_point():
    main()

__starting_point()

MAX = 100005

def big_pow3(n):
    l = 0; p = MAX
    while p-l != 1:
        mid = (p+l+1)//2
        if (mid*mid*mid <= n):
            l = mid
        else:
            p = mid
    return l

def f(n):
    if n < 8:
        return [n, n]
    a = int((n+ 0.5) ** 0.33333333333333333)
    r1 = f(n-a**3)
    r1 = [r1[0] + 1, r1[1] + a**3]
    a -= 1
    r2 = f(3*a*(a+1))
    r2 = [r2[0] + 1, r2[1] + a**3]
    return max(r1, r2)
        

def __starting_point():
    m = int(input()) 
    print(*f(m))

__starting_point()

n, c = 0, 0
def dfs(now, m, t):
	nonlocal n, c
	if now == 0:
		if m > n:
			n, c = m, t
		return
	i = 1
	while i**3 <= now:
		i += 1
	i -= 1
	dfs(now-i**3, m+1, t+i**3)
	dfs(i**3-1-(i-1)**3, m+1, t+(i-1)**3)
m = int(input())
dfs(m, 0, 0)
print(n, c)


n, c = 0, 0
def dfs(now, m, t):
	nonlocal n, c
	if now == 0:
		if m > n:
			n, c = m, t
		return
	i = 1
	while i**3 <= now:
		i += 1
	i -= 1
	dfs(now-i**3, m+1, t+i**3)
	dfs(i**3-1-(i-1)**3, m+1, t+(i-1)**3)
m = int(input())
dfs(m, 0, 0)
print(n, c)

n, c = 0, 0
def dfs(now, m, t):
	nonlocal n, c
	if now == 0:
		if m > n:
			n, c = m, t
		return
	i = 1
	while i**3 <= now:
		i += 1
	i -= 1
	dfs(now-i**3, m+1, t+i**3)
	dfs(i**3-1-(i-1)**3, m+1, t+(i-1)**3)
m = int(input())
dfs(m, 0, 0)
print(n, c)

n, c = 0, 0
def dfs(now, m, t):
	nonlocal n, c
	if now == 0:
		if m > n:
			n, c = m, t
		return
	i = 1
	while i**3 <= now:
		i += 1
	i -= 1
	dfs(now-i**3, m+1, t+i**3)
	dfs(i**3-1-(i-1)**3, m+1, t+(i-1)**3)
m = int(input())
dfs(m, 0, 0)
print(n, c) 

m = int(input())

def rec(m):
    if m < 0:
        return -1, 0
    if m == 0:
        return 0, 0
    a = int((m + 1e-9) ** (1 / 3))
    u = m - a ** 3
    v = a ** 3 - (a - 1) ** 3 - 1
    x, y = rec(u)
    q, w = rec(v)
    return max((x + 1, a ** 3 + y), (q + 1, (a - 1) ** 3 + w))

print(*rec(m))

def rec(m):
    if m <= 0:
        return m, 0
    a = int((m + 1e-9) ** (1 / 3))
    x, y = rec(m - a ** 3)
    q, w = rec(a ** 3 - (a - 1) ** 3 - 1)
    return max((x + 1, a ** 3 + y), (q + 1, (a - 1) ** 3 + w))
print(*rec(int(input())))

import math

def f(m):
    if m < 8: return (m,m)
    c = math.floor(m**(1.0/3))
    if not (c**3 <= m and m < (c+1)**3):
        if ((c+1)**3 <= m and m < (c+2)**3):
            c = c+1
        elif ((c-1)**3 <= m and m < c**3):
            c = c-1
        else:
            assert False
    ans1, x1 = f(m-c**3)
    ans2, x2 = f(c**3-1-(c-1)**3)
    return max((1+ans1,x1+c**3), (1+ans2,x2+(c-1)**3))

def __starting_point():
    m = int(input())

    print(*f(m))

__starting_point()

def g(m, s, n):
    k = int(m ** (1 / 3))
    if m == 0 or k == 1: return s + m, n + m
    x, y = k ** 3, (k - 1) ** 3
    a = g(m - x, s + x, n + 1)
    b = g(x - y - 1, s + y, n + 1)
    return b if a[1] < b[1] else a
s, n = g(int(input()), 0, 0)
print(n, s)

import math

def root(m):
	ret = m**(1.0/3.0)
	if(math.ceil(ret)**3 == m):
		ret = math.ceil(ret)
	else: ret = math.floor(ret)
	return ret

F = {}

def f(m):
	if(m < 0):
		return [-1e5 - 10, -1e15 - 1]
	if(m <= 7):
		return [m, m]
	rootm = root(m)
	ans1 = [0, 0]
	ans2 = [0, 0]
	ans1 = f(m - rootm**3)
	if(rootm != 1):
		ans2 = f(rootm**3 - 1 - (rootm-1)**3);
		ans2[1] += (rootm-1)**3;
		ans2[0] += 1;
	ans1[1] += rootm**3;
	ans1[0] += 1;
	if(ans1[0] > ans2[0]):
		return ans1
	elif(ans1[0] < ans2[0]):
		return ans2
	else:
		if(ans1[1] > ans2[1]):
			return ans1
		else:
			return ans2

m = int(input())
ans = f(m)
print(ans[0], ans[1])



def cube(a):
    return a ** 3


def steps(m):
    if m <= 7:
        return m
    x = 1
    while cube(x + 1) <= m:
        x += 1
    return  1 + steps(max(m - cube(x), cube(x) - 1 - cube(x - 1)))


class CodeforcesTask679BSolution:
    def __init__(self):
        self.result = ''
        self.m = 0

    def read_input(self):
        self.m = int(input())

    def process_task(self):
        sub = 0
        ste = 0
        while self.m:
            ste += 1
            x = 1
            while cube(x + 1) <= self.m:
                x += 1
            if steps(self.m) == 1 + steps(self.m - cube(x)):
                self.m -= cube(x)
                sub += cube(x)
            else:
                self.m = cube(x) - 1 - cube(x - 1)
                sub += cube(x - 1)
        self.result = "{0} {1}".format(ste, sub)

    def get_result(self):
        return self.result


def __starting_point():
    Solution = CodeforcesTask679BSolution()
    Solution.read_input()
    Solution.process_task()
    print(Solution.get_result())

__starting_point()