eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 1 second
Memory limit 64 MiB

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

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

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

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

Input data

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

Output data

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

Examples

Input example #1
1
Output example #1
1
Author Alexei Tolstikov