e-olymp
Competitions

Knapsack - Рюкзак

Decomposition into a sum of cubes

Given a positive integer n, decompose it to the sum of minimum number of positive perfect cubes. The program should print this minimum quantity.

Input

One single positive integer n (1n106).

Output

Print one positive integer - the minimum quantity of cubes.

Time limit 1 seconds
Memory limit 128 MiB
Input example #1
33
Output example #1
5

Example description: 33=2^3+2^3+2^3+2^3+1^3, and 33 cannot be decomposed into a sum of less than five positive cubes.

Author Илья Порублёв
Source Летняя школа Севастополь 2013, Волна 1, День 2