cho.sh

Problem

Hexagonal numbers can be defined by arranging points in hexagonal shapes. Let $h_n$ be the number of distinct points that appear when hexagons with 1, 2, ..., $n$ points on a side are drawn so that only one point overlaps.

The figure shows $h_1$ , $h_2$ , $h_3$ , and $h_4$ in order. The first six hexagonal numbers are 1, 6, 15, 28, 45, and 66.

Given a positive integer $N$ , find the minimum number of hexagonal numbers whose sum is $N$ .

N	Minimum count	Sum
1	1	1
2	2	1+1
3	3	1+1+1
4	4	1+1+1+1
5	5	1+1+1+1+1
6	1	6
7	2	1+6
8	3	1+1+6
9	4	1+1+1+6
10	5	1+1+1+1+6
11	6	1+1+1+1+1+6
12	2	6+6

Every integer greater than 1791 can be represented as the sum of four hexagonal numbers. Also, every sufficiently large number can be represented as the sum of three hexagonal numbers. For every positive integer, the minimum count is at most 6, and only 11 and 26 have minimum count 6. The largest number with answer 6 is 26, the largest number with answer 5 is 130, and the largest number with answer 4 is 146858.

Input

The first line contains the positive integer $N$ .

Output

Print the minimum number of hexagonal numbers needed to make $N$ .

Constraints

$1 \le N \le 1,000,000$

Hexagonal Numbers

Problem

Input

Output

Constraints