Задача C. Треугольное домино ≡

Условие

Тимофей очень любит играть в домино со своими друзьями. К сожалению, сыграв множество партий, друзья перепробовали все разновидности доминошных игр, узнали все стратегии и тактические ходы, сильные и слабые стороны друг друга... Короче говоря, играть стало неинтересно.

Поговорив с родителями, Тимофей узнал, что на свете придумано множество настольных игр, где используются нестандартные костяшки. Посетив несколько тематических форумов, он остановил свой выбор на треугольном домино или тримино. Как и в традиционном домино, в ней есть костяшки, только они треугольной формы. В углах костяшек выписаны цифры от 0 до n, при этом против часовой стрелки цифры идут в неубывающем порядке, и все костяшки разные.

Стандартный набор традиционного тримино включает в себя 56 костяшек. В полном наборе представлены все комбинации троек чисел от 0 до 5. Тимофей выяснил, что в специализированных наборах тримино возможное число n может быть произвольным.

Родители заказали для Тимофея особый набор тримино и держат в секрете, какое наибольшее число может быть расположено в угле костяшки. Однако Тимофей выяснил общее количество костяшек в наборе. Помогите Тимофею раскрыть секрет и узнать значение n.

Формат входных данных

В единственной строке входного файла записано натуральное число k  — количество костяшек в полном наборе.

Формат выходных данных

В единственной строке выходного файла запишите одно целое неотрицательное число  — наибольшее число, которое может быть расположено на костяшках такого набора. Гарантируется, что такой ответ существует.

Ограничения

Система оценки и описание подзадач

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Подзадача 1: 1 ≤ k ≤ 10⁵, баллы: 50.

Подзадача 2: нет дополнительных ограничений, баллы: 50.

Пояснения к примерам

В первом примере полный набор состоит из единственной костяшки "0-0-0". Наибольшее число в углу костяшки  — 0.

Во втором примере в полном наборе из 10 костяшек будут следующие: "0-0-0", "1-0-0", "1-1-0", "1-1-1", "2-0-0", "2-1-0", "2-1-1", "2-2-0", "2-2-1", "2-2-2". Наибольшее число в углу костяшки  — 2.

В третьем примере в стандартном наборе тримино, наибольшее число в углу костяшки равно пяти. Полный набор составляет 56 костяшек.

Примеры тестов

1

0

10

2

56

5