캡틴 이다솜

캡틴 이다솜은 해적선에 적을 공격할 대포알을 많이 보관해 둔다. 미적 감각이 뛰어난 이다솜은 대포알을 반드시 사면체 모양으로 쌓아야 한다고 생각한다.

크기 N의 더미는 한 변의 길이가 N인 정삼각형 층을 바닥에 놓고, 그 위에 한 변의 길이가 N-1인 정삼각형 층을 올리는 방식으로 만든다. 이 과정을 반복해 마지막에는 한 변의 길이가 1인 정삼각형 층을 올린다.

크기가 3인 더미는 다음과 같다.

  X

  X
 X X

  X
 X X
X X X

각 정삼각형 층에 들어가는 대포알 수는 1, 3, 6, 10, ...개이다. 따라서 완성된 사면체 하나에 들어가는 대포알 수는 1, 4, 10, 20, ...개이다.

현재 해적선에는 대포알이 N개 있다. 이다솜은 영식이에게 이 대포알로 사면체 더미들을 만들라고 했다. 영식이는 가능한 한 적은 수의 사면체를 만들려고 한다. N개의 대포알을 모두 사용해서 만들 수 있는 사면체 개수의 최솟값을 구하시오.

첫째 줄에 자연수 N이 주어진다. N은 300,000보다 작거나 같다.

첫째 줄에 N개의 대포알을 모두 사용해 만들 수 있는 사면체 개수의 최솟값을 출력한다.