e-olymp
Задачи

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

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

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

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

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

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

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

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

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

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

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
1
Выходные данные #1
1