Император ацтеков Куитлауак собирается построить пирамиду в свою честь. Эта пирамида должна быть выше, чем предыдущие.

Пирамида Ацтеков строится из каменных блоков. Каждый блок представляет собой куб размером 1 × 1 × 1. Куитлауак размещает первый блок на земле во время церемонии заложения пирамиды. Каждый из следующих блоков должен полностью прилегать к грани хотя бы одного из предыдущих блоков.

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

Куитлауак просит Вас определить высоту самой высокой стабильной пирамиды, которую можно построить из имеющегося набора блоков.

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

Содержит количество имеющихся блоков n (1 ≤ n ≤ 109), включая первый.

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

Выведите высоту самой высокой устойчивой пирамиды, которая может быть построена из n блоков.