Автор: | Антон Карабанов | Ограничение времени: | 3 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 64 Мб | |
Выходной файл: | Стандартный выход | |||
Максимальный балл: | 100 |
Антону нужно перевезти из одного города в другой партию из n новогодних хлопушек. В соответствии с правилами транспортной безопасности ГОСТ-202021, перевозить их можно только партиями в кубических коробках (куда поместится k × k × k хлопушек, то есть 1, 8, 27, 64, ... ) или в почти кубических коробках (куда поместится k × k × (k − 1) хлопушек, то есть 4, 18, 48, ... ). Коробки должны быть заполнены полностью.
У Антона есть по одной коробке любого разрешенного вида. Помогите ему определить минимальное количество коробок, которое понадобится при перевозке.
Единственная строка входного файла содержит натуральное число n — количество хлопушек.
Выведите одно натуральное число — ответ на задачу. Если перевезти все хлопушки невозможно — выведите число -1.
1 ≤ n ≤ 105
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n ≤ 100, получат не менее 40 баллов.
В первом примере Антону требуется перевезти 58 хлопушек. Он может разложить их по коробкам таким образом: 27 + 18 + 8 + 4 + 1. Меньшим числом коробок обойтись нельзя.
Во втором примере Антону не удастся разложить 43 хлопушки по коробкам.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|