Однажды утром Глеб с ужасом осознал, что проспал, а пары в «Высшем университете» начинаются уже скоро. Опоздать было бы не так страшно, если бы он их и не вёл. К счастью, автомобиль Глеба «Пантера» довольно мощный: для упрощения будем считать, что за одну секунду он может сначала или увеличить скорость на $$$1$$$, или уменьшить скорость на $$$1$$$, или не менять её, а после этого его автомобиль проезжает $$$x$$$ метров, где $$$x$$$ — его текущая скорость в метрах в секунду. Потом он снова принимает решение об изменении скорости. Начальная скорость автомобиля преподавателя в момент, когда он только выезжает из дома, равна нулю. Путь до университета от его дома не близкий: нужно проехать $$$d$$$ метров.
Глеб, обеспокоенный за знания своих студентов, хочет попасть в университет как можно раньше, чтобы успеть подготовиться к проведению лекции. К сожалению, на проезде на парковку университета установлен шлагбаум, поэтому скорость автомобиля после того, как он проехал ровно $$$d$$$ метров должна быть равна $$$0$$$.
Пока Глеб собирался на работу, его заинтересовал вопрос, а за какое минимальное время он может доехать до работы, если будет действовать оптимально. Так как преподаватель будет занят скоростным вождением, ответить на этот вопрос честь выпала вам!
Вводится одно целое число — $$$d$$$ ($$$1 \leq d \leq 10^{18}$$$), расстояние до университета.
Обратите внимание, что входные данные могут быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать и с типом int.
Выведите единственное целое число — исходное минимальное время, за которое Глеб может доехать до университета, в точности остановившись перед шлагбаумом.
2
3
10
7
В первом тесте из условия Глебу выгодно действовать следующим образом:
Таким образом, он потратит $$$3$$$ секунды, и его конечная скорость будет равно $$$0$$$ м/с. Во втором тесте из условия Глебу выгодно действовать, например, так:
Таким образом, он потратит $$$7$$$ секунд, и его конечная скорость будет равно $$$0$$$ м/с.
В данной задаче $$$25$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$4$$$ балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие при $$$1 \leq d \leq 10^2$$$, наберут не менее $$$20$$$ баллов
Решения, корректно работающие при $$$1 \leq d \leq 10^4$$$, наберут не менее $$$40$$$ баллов.
Решения, корректно работающие при $$$1 \leq d \leq 10^9$$$, наберут не менее $$$60$$$ баллов.
Решения, корректно работающие при $$$1 \leq d \leq 10^{12}$$$, наберут не менее $$$80$$$ баллов.