Solarium for mushrooms (Hard)
And again Michael does his experiments. This time he decided to clone the mushrooms. For this, he prepared n spores, which soon will plant in the ground and grow. When spores will develop and increase in size, they haven't touch each other, so Michael decided to plant them only at integer coordinates. And also to speed up the growth process, he is going to build a large round lamp to warm them. The center of the lamp he wants to place at point with integer coordinates, and let the radius of the lamp be integer too. But how to define it? Of course, you can build a lamp under which the whole forest can be hidden, but it will take a lot of extra time. So, the radius of the lamp must be as small as possible.
Input
The number of spores n (0 ≤ n ≤ 3141592649625).
Output
Print the smallest integer radius of the lamp, under which all the n spores can hide.