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: HARD
Tags: Dynamic programming

Sorting

Greedy algorithms
Skill types: Dynamic programming

Sorting

Greedy algorithms

Starter code:

Solutions:
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.3333333333333333)
	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()


def main():

	def f(n):
		if n < 8:
			return [n, n]
		a = int((n + 0.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()


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
Solution = CodeforcesTask679BSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


im = int(input())
best_steps = 0
best_length = 0

def rec(m, steps, substracted):
	global 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)


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))
m = int(input())
print(*f(m))


def f(m, cnt, y):
	global ans, x
	if m == 0:
		(ans, x) = max((ans, x), (cnt, y))
		return
	a = int(m ** (1 / 3))
	(k1, k2) = (a ** 3, (a - 1) ** 3)
	f(m - k1, cnt + 1, y + k1)
	f(k1 - k2 - 1, cnt + 1, y + k2)
m = int(input())
(ans, x) = (0, m)
f(m, 0, 0)
print(ans, x)


from sys import *
setrecursionlimit(1000000)

def c(n):
	if n < 8:
		return (n, n)
	t1 = int(n ** (1 / 3) + 1e-11)
	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
	return v1
print(' '.join(map(str, c(int(input())))))


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 [-100000.0 - 10, -1000000000000000.0 - 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
	elif ans1[1] > ans2[1]:
		return ans1
	else:
		return ans2
m = int(input())
ans = f(m)
print(ans[0], ans[1])


import math

def steps(m, dct):
	if m <= 7:
		return m
	if dct.get(m):
		return dct[m]
	x = math.floor(m ** (1 / 3))
	dct[m] = 1 + steps(max(m - x ** 3, x ** 3 - 1 - (x - 1) ** 3), dct)
	return dct[m]
m = int(input())
total_blocks_used = 0
total_vol = 0
steps_dct = {}
while m > 0:
	x = math.floor(m ** (1 / 3))
	if steps(m, steps_dct) == 1 + steps(m - x ** 3, steps_dct):
		m -= x ** 3
		total_vol += x ** 3
	else:
		m = x ** 3 - 1 - (x - 1) ** 3
		total_vol += (x - 1) ** 3
	total_blocks_used += 1
print(f'{total_blocks_used} {total_vol}')


def rec(m):
	if m <= 0:
		return (m, 0)
	a = int((m + 1e-09) ** (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())))


def kil(n):
	if n < 8:
		return (n, n)
	m = int(n ** (1 / 3))
	(k1, v1) = kil(n - m * m * m)
	(k2, v2) = kil(m * m * m - 1 - (m - 1) * (m - 1) * (m - 1))
	return (k1 + 1, v1 + m * m * m) if (k1, v1 + m * m * m) > (k2, v2 + (m - 1) * (m - 1) * (m - 1)) else (k2 + 1, v2 + (m - 1) * (m - 1) * (m - 1))
n = int(input())
print(*kil(n))


def func(n):
	if n < 8:
		return (n, n)
	max_a = int(n ** (1 / 3))
	if (max_a + 1) ** 3 <= n:
		max_a += 1
	v1 = func(n - max_a ** 3)
	v1 = (v1[0] + 1, v1[1] + max_a ** 3)
	v2 = func(max_a ** 3 - 1 - (max_a - 1) ** 3)
	v2 = (v2[0] + 1, v2[1] + (max_a - 1) ** 3)
	if v2 > v1:
		return v2
	else:
		return v1
print(' '.join(map(str, func(int(input())))))


import sys

def cube_root(x):
	v = max(int(x ** (1.0 / 3.0)) - 1, 0)
	while (v + 1) ** 3 <= x:
		v += 1
	return v

def solution(x):
	if x <= 7:
		return (x, x)
	next_smaller = cube_root(x) ** 3
	candidate = solution(x - next_smaller)
	candidate = (candidate[0] + 1, candidate[1] + next_smaller)
	prenext_smaller = cube_root(next_smaller - 1) ** 3
	if next_smaller - prenext_smaller > x - next_smaller:
		candidate2 = solution(next_smaller - 1)
	else:
		candidate2 = candidate
	if candidate >= candidate2:
		return candidate
	else:
		return candidate2
n = int(input())
s = solution(n)
print(s[0], s[1])


def kil(n):
	if n < 8:
		return (n, n)
	m = 2
	while m * m * m <= n:
		m += 1
	m -= 1
	(k1, v1) = kil(n - m * m * m)
	(k2, v2) = kil(m * m * m - 1 - (m - 1) * (m - 1) * (m - 1))
	return (k1 + 1, v1 + m * m * m) if (k1, v1 + m * m * m) > (k2, v2 + (m - 1) * (m - 1) * (m - 1)) else (k2 + 1, v2 + (m - 1) * (m - 1) * (m - 1))
n = int(input())
print(*kil(n))


from math import *
from sys import *
N = int(input())
memo = {}

def solve(n, R):
	if n in memo:
		return memo[n]
	if n == 0:
		return (0, 0)
	s = floor(pow(n, 1 / 3) - 1)
	while (s + 1) ** 3 <= n:
		s += 1
	(A, B) = solve(n - s ** 3, 5)
	if R > 0:
		(C, D) = solve(s ** 3 - 1, R - 1)
	else:
		(C, D) = (0, 0)
	memo[n] = max((A + 1, B + s ** 3), (C, D))
	return memo[n]
(A, B) = solve(N, 5)
print(A, B)


def g(m, n, s):
	if not m:
		return (n, s)
	k = int(m ** (1 / 3))
	(x, y) = (k ** 3, (k - 1) ** 3)
	return max(g(m - x, n + 1, s + x), g(x - y - 1, n + 1, s + y))
print(*g(int(input()), 0, 0))


from math import *

class sqrt_decomp:

	def _init_(self, val):
		self.values = val
		self.blockl = int(sqrt(len(val)))
		self.noblocks = int(ceil(len(val) / self.blockl))
		self.plusv = [0] * self.noblocks
		self.sumbl = [0] * self.noblocks
		for i in range(self.noblocks):
			self.sumbl = sum(val[i * self.blockl:max(len(val), (i + 1) * self.blockl)])

def maximize(n, X, l):
	if l == 0:
		return 0
	cur = ans[l - 1]
	X -= cur ** 3
	while X + (cur + 1) ** 3 <= n:
		cur += 1
	Xy = cur ** 3
	Xy += maximize(min(n - Xy, (cur + 1) ** 3 - Xy - 1), X, l - 1)
	ans[l - 1] = cur
	return Xy
n = int(input())
c = 1
ans = []
X = 0
while X + c ** 3 <= n:
	while X < (c + 1) ** 3 - c ** 3 and X + c ** 3 <= n:
		ans += [c]
		X += c ** 3
	c += 1
X = maximize(n, X, len(ans))
print(len(ans), X)


import math
m = int(input())

def get_max_edge(x):
	c = x ** (1 / 3.0)
	return math.floor(c)
max_blocks = 0
max_volume = 0

def solve(m, blocks, volume):
	global max_blocks, max_volume
	if m == 0:
		if blocks > max_blocks or (blocks == max_blocks and volume > max_volume):
			max_blocks = blocks
			max_volume = volume
		return
	x = get_max_edge(m)
	solve(m - x ** 3, blocks + 1, volume + x ** 3)
	if x > 1:
		solve(x ** 3 - 1 - (x - 1) ** 3, blocks + 1, volume + (x - 1) ** 3)
solve(m, 0, 0)
print(max_blocks, max_volume)


import math
import sys

def get_next(x):
	t = (-3 + math.sqrt(12 * x - 3)) / 6.0
	t = math.floor(t)
	for i in range(max(t - 6, 1), t + 7):
		nx = x + i ** 3
		if nx < (i + 1) ** 3:
			return nx
	assert False
min_by_level = [0, 1]
for i in range(2, 20):
	min_by_level.append(get_next(min_by_level[-1]))
high = int(input())
level = 1
while min_by_level[level] <= high:
	level += 1
level -= 1
ans_level = level
ans_number = 0
for i in range(level - 1, -1, -1):
	le = 1
	rg = 10 ** 5 + 1
	while rg - le > 1:
		mid = (rg + le) // 2
		if high - mid ** 3 >= min_by_level[i]:
			le = mid
		else:
			rg = mid
	ans_number += le ** 3
	high = min(high - le ** 3, (le + 1) ** 3 - 1 - le ** 3)
print(ans_level, ans_number)


B = (0, 0)

def solve(rem, step, sub):
	global B
	if rem == 0:
		B = max(B, (step, sub))
		return
	cnt = 1
	while (cnt + 1) ** 3 <= rem:
		cnt += 1
	solve(rem - cnt ** 3, step + 1, sub + cnt ** 3)
	if cnt > 0:
		solve(cnt ** 3 - 1 - (cnt - 1) ** 3, step + 1, sub + (cnt - 1) ** 3)
x = int(input())
solve(x, 0, 0)
print(B[0], B[1])


(n, c) = (0, 0)

def dfs(now, m, t):
	global 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)


def c(n):
	if n < 8:
		return (n, n)
	t1 = int(n ** (1 / 3) + 1e-11)
	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
	return v1
print(' '.join(map(str, c(int(input())))))


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)