Pyramid Construction

Interview

Time limit1sMemory limit1024 MB

Summary

Given N blocks, find the largest height h whose layers 1^2 + 3^2 + ... + (2h-1)^2 use at most N blocks.

Level: Easy2 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

When starting a large project such as building a pyramid, it is best to think once more. Write a program that computes the height of the tallest pyramid you can build with a given number of stone blocks.

The pyramid is compact, so there are no hollow spaces inside. It is built by the principle shown in Figure 1. Each layer is a square whose side is two blocks shorter than the layer below it. The top layer always consists of a single block.

Figure 1: An example of a pyramid of height 3 with 35 blocks.

It does not matter if blocks are left over, but not a single block may be missing.

Input

The input is a single integer $N$ ( $1 \le N \le 100\,000\,000$ ), the number of blocks available.

Output

Print one line with one integer: the height of the tallest pyramid that can be built with at most $N$ blocks.

Examples1

Example 1
Input
```
83
```
Expected output
```
3
```