Hexagonal Numbers

Time limit2sMemory limit128 MB

Summary

Given N up to 1,000,000, compute the minimum number of hexagonal numbers (1, 6, 15, 28, ...) that sum to N.

Level: Medium6 of 10
Topics: Dynamic programming, Math, Number theory, BFS
Solved: No attempts yet

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$

Examples6

Example 1
Input
```
26
```
Expected output
```
6
```
Example 2
Input
```
130
```
Expected output
```
5
```
Example 3
Input
```
146858
```
Expected output
```
4
```
Example 4
Input
```
999999
```
Expected output
```
3
```
Example 5
Input
```
1000000
```
Expected output
```
2
```
Example 6
Input
```
145530
```
Expected output
```
1
```