#81 cubesum

Loading problem...

Preparing the statement, recent submissions, and submit form.

#81 cubesum | DOJ

Authors: Admin

Statement

양의 정수 $n$ 이 주어진다.

$n$ 을 하나 이상의 양의 세제곱수의 합으로 나타내려고 한다. 즉, 다음을 만족하는 자연수 $k$ 와 자연수 $a_1, a_2, \dots, a_k$ 를 찾고자 한다.

n = a_1^3 + a_2^3 + \cdots + a_k^3

이때 가능한 $k$ 의 최솟값을 구하여라.

첫째 줄에 양의 정수 $n$ 이 주어진다.

$n$ 을 양의 세제곱수들의 합으로 나타내기 위해 필요한 항의 개수의 최솟값을 출력한다.

$1 \le n \le 10^{10}$

#	Score	Constraints
1	100	-

Sample 1

Input

Output

Sample 2

Input

Output

Sample 3

Input

8884844

Output

Sample 4

Input

10000000000

Output