Captain Dasom

Interview

Time limit2sMemory limit128 MB

Summary

Given N cannonballs, find the minimum number of tetrahedral-number piles whose sizes sum exactly to N using unbounded coin-change style DP.

Level: Medium5 of 10
Topics: Dynamic programming, Math, Combinatorics
Solved: No attempts yet

Problem

Captain Dasom keeps many cannonballs on a pirate ship for attacking enemies. Because Dasom has a strong sense of aesthetics, the cannonballs must be stacked as tetrahedrons.

A pile of size N is built by placing an equilateral triangular layer with side length N on the bottom, then a layer with side length N-1 on top of it, and so on until the top layer has side length 1.

A pile of size 3 looks like this.

  X

  X
 X X

  X
 X X
X X X

The numbers of cannonballs in the triangular layers are 1, 3, 6, 10, ... . Therefore, a completed tetrahedron contains 1, 4, 10, 20, ... cannonballs.

There are N cannonballs on the ship. Dasom asks Youngsik to use them to build tetrahedral piles. Youngsik wants to build as few tetrahedrons as possible. Find the minimum number of tetrahedrons that can be made while using all N cannonballs.

Input

The first line contains a natural number N. N is at most 300,000.

Output

Print the minimum number of tetrahedrons that can be made while using all N cannonballs.

Examples5

Example 1
Input
```
15
```
Expected output
```
3
```
Example 2
Input
```
1
```
Expected output
```
1
```
Example 3
Input
```
5
```
Expected output
```
2
```
Example 4
Input
```
9
```
Expected output
```
3
```
Example 5
Input
```
91
```
Expected output
```
2
```