Девочка со спичками

Однажды с девочкой Таней случилась следующая история. На уроке математики задали домашнее задание склеить K различных треугольников с целочисленными сторонами, причем эти треугольники нужно было склеить из спичек.

Казалось бы, задание выполнить нереально, особенно для больших значений K. Но нашей Тане повезло - папа у Тани коллекционирует спички. У папы есть много коробков со спичками, количество спичек в каждом коробке равно 10¹⁵, причем все спички в одном коробке имеют одинаковую длину. Коллекция у Таниного папы очень хорошая - для каждого L от 1 до 10¹⁰ включительно в коллекции есть ровно один коробок, в котором спички имеют длину L.

Естественно, папа очень дорожит своей коллекцией, причем ценность коробка возрастает с длиной спичек, лежащих в нем. Таня хочет попросить у папы N коробков, и папа в этом случае, конечно, даст ей коробки со спичками, имеющими длину от 1 до N. Таня очень любит папу, поэтому хочет попросить у него минимальное количество коробков. Помогите Тане определить, сколько коробков ей нужно попросить.

Треугольник из спичек с длинами a ≤ b ≤ c можно склеить тогда и только тогда, когда c < a + b.

Входные данные

Целое число K (1 ≤ K ≤ 10¹²)- количество различных треугольников, которые должна склеить Таня.

Выходные данные

Целое число N, равное минимальному количеству коробков, которые должна попросить Таня у папы для выполнения домашнего задания.