eolymp
Competitions

1/8 ICPC Azerbaijan Qualification Preparation

Aztec Pyramid

Aztec emperor Cuitlahuac is going to build a pyramid in his honor. This pyramid should be taller than previous ones.

The Aztec pyramid is build out of stone blocks. Each block is 1 × 1 × 1-hunab cube. Cuitlahuac places first block on the ground during the foundation ceremony. Each of the following blocks must share a face with at least one of the previous blocks.

prb3889.gif

The block is stable if it stands on the ground, or it stands on another block, that has a block or the ground next to each face. To stand the test of time the pyramid must be stable i.e. each block of it must be stable.

prb3889_1.gif

Cuitlahuac asks you to determine the height of the tallest stable pyramid that can be built out of available blocks.

Input

Contains the number n (1n109) of available blocks, including the first one.

Output

Print the height of the tallest stable pyramid that may be built out of n blocks. The height must be output in hunabs.

Time limit 1 second
Memory limit 128 MiB
Input example #1
6
Output example #1
2
Input example #2
5
Output example #2
1
Input example #3
20
Output example #3
3
Source 2012 ACM NEERC, Northern Subregion, November 3, Problem A