Aztec Pyramid
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.
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.
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 (1 ≤ n ≤ 109
) 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.
6
2
5
1
20
3