Солярий для Грибов (Hard)
И снова Михаил проводит свои эксперименты. В этот раз он решил клонировать грибы. Для этого он приготовил n спор, которые в скором времени посадит в землю и вырастит. Чтобы споры, развиваясь и увеличиваясь в размерах, не мешали друг другу, Михаил решил садить их только в целочисленных координатах. А также, чтобы ускорить процесс роста, он собирается построить большую круглую лампу, которая будет греть его подрастающие копии. Центр лампы он тоже разместит над точкой с какими-нибудь целочисленными координатами, да и радиус лампы тоже пусть будет целым. Вот только как его определить? Конечно, можно построить лампу, под которой поместится и весь лес, но на это уйдёт много лишнего времени, а времени у Михаила не так много. Так что, радиус лампы должен быть как можно меньше.
Входные данные
Количество спор n (0 ≤ n ≤ 3141592649625).
Выходные данные
Выведите минимально возможный целочисленный радиус лампы, под которой поместятся все n спор.