Девочка со спичками
Однажды с девочкой Таней случилась следующая история. На уроке математики задали домашнее задание склеить K различных треугольников с целочисленными сторонами, причем эти треугольники нужно было склеить из спичек.
Казалось бы, задание выполнить нереально, особенно для больших значений K. Но нашей Тане повезло - папа у Тани коллекционирует спички. У папы есть много коробков со спичками, количество спичек в каждом коробке равно 10^15, причем все спички в одном коробке имеют одинаковую длину. Коллекция у Таниного папы очень хорошая - для каждого L от 1 до 10^10 включительно в коллекции есть ровно один коробок, в котором спички имеют длину L.
Естественно, папа очень дорожит своей коллекцией, причем ценность коробка возрастает с длиной спичек, лежащих в нем. Таня хочет попросить у папы N коробков, и папа в этом случае, конечно, даст ей коробки со спичками, имеющими длину от 1 до N. Таня очень любит папу, поэтому хочет попросить у него минимальное количество коробков. Помогите Тане определить, сколько коробков ей нужно попросить.
Треугольник из спичек с длинами a ≤ b ≤ c можно склеить тогда и только тогда, когда c < a + b.
Входные данные
Целое число K (1 ≤ K ≤ 10^12)- количество различных треугольников, которые должна склеить Таня.
Выходные данные
Целое число N, равное минимальному количеству коробков, которые должна попросить Таня у папы для выполнения домашнего задания.