Задача C. Хлопушки ≡

Условие

Антону нужно перевезти из одного города в другой партию из n новогодних хлопушек. В соответствии с правилами транспортной безопасности ГОСТ-202021, перевозить их можно только партиями в кубических коробках (куда поместится k × k × k хлопушек, то есть 1, 8, 27, 64, ... ) или в почти кубических коробках (куда поместится k × k × (k − 1) хлопушек, то есть 4, 18, 48, ... ). Коробки должны быть заполнены полностью.

У Антона есть по одной коробке любого разрешенного вида. Помогите ему определить минимальное количество коробок, которое понадобится при перевозке.

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

Единственная строка входного файла содержит натуральное число n — количество хлопушек.

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

Выведите одно натуральное число — ответ на задачу. Если перевезти все хлопушки невозможно — выведите число -1.

Ограничения

1 ≤ n ≤ 10⁵

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

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 100, получат не менее 40 баллов.

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

В первом примере Антону требуется перевезти 58 хлопушек. Он может разложить их по коробкам таким образом: 27 + 18 + 8 + 4 + 1. Меньшим числом коробок обойтись нельзя.

Во втором примере Антону не удастся разложить 43 хлопушки по коробкам.

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

58

5

43

-1