육각수 · cho.sh

문제

육각수는 육각형 모양으로 점을 배열해 정의한다. $h_n$ 은 한 변에 점이 1개, 2개, ..., $n$ 개인 육각형들을 한 점만 겹치도록 그렸을 때 나타나는 서로 다른 점의 개수이다.

그림은 $h_1$ , $h_2$ , $h_3$ , $h_4$ 를 차례로 나타낸다. 처음 여섯 육각수는 1, 6, 15, 28, 45, 66이다.

자연수 $N$ 이 주어질 때, 합이 $N$ 이 되도록 선택해야 하는 육각수의 최소 개수를 구하라.

N	최소 개수	합
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

1791보다 큰 모든 정수는 육각수 4개의 합으로 나타낼 수 있다. 또한 충분히 큰 수는 항상 육각수 3개의 합으로 나타낼 수 있다. 어떤 자연수라도 필요한 육각수의 최소 개수는 6 이하이며, 최소 개수가 6인 수는 11과 26뿐이다. 답이 6인 가장 큰 수는 26, 답이 5인 가장 큰 수는 130, 답이 4인 가장 큰 수는 146858이다.

입력

첫째 줄에 자연수 $N$ 이 주어진다.

출력

$N$ 을 만들기 위해 필요한 육각수 개수의 최솟값을 출력한다.

제한

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