Migrated from Lutece 1558 Destr0y City

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Alice want to build $n$ cities on a plane. A city can be regarded as a point. In order to keep communication between cities, the distance between each pair of cities must NOT greater than $D$.

Bob has a weapon which can destroy all the cities in a circle with radius $R$. After Alice building all the cities, Bob will select a city as the center and use his weapon once, and he will choose a way such that can destroy as many cities as possible.

To prevent the cities from being destroyed, Alice want choose a way to build her cities such that the number of cities will be destroyed by Bob can be as little as possible, can you tell her how to build these cities?

In order to make the problem easier, you can assume that $D = \sqrt{2}R$ is always established, so the specific values of $D$ and $R$ will not affect the answer.

Input

Only one line contains an integer $n$.

$1 \leq n \leq 10^{18}$.

Output

The number of cities will be destroyed by Bob if Alice choose the optimal scheme to build her cities.

Samples

3

1

Resources

The 15th UESTC Programming Contest Preliminary