Solarium for mushrooms (Hard)#4361
Once again, Mikhail is conducting his experiments. This time, he decided to clone mushrooms. For that, he prepared spores, which he will soon plant in the ground and grow. To ensure that the spores, as they grow and expand, do not interfere with each other, Mikhail decided to place them only at points with integer coordinates.
In addition, to accelerate their growth, he plans to build a large circular lamp that will warm the developing mushrooms. He also wants to place the center of the lamp at a point with integer coordinates, and the lamp's radius should also be an integer.
But how should he choose the appropriate radius? Of course, he could build a lamp large enough to cover the entire mushroom forest, but that would take a lot of extra time — and Mikhail doesn't have much time to spare. Therefore, the radius of the lamp should be as small as possible.
A single integer is given — the number of spores n~(0 \le n \le 3141592649625).
Output the smallest possible integer radius of a lamp that can cover all spores.
Example 1