Задача D. Башня из банок

Автор:Завгороднев А.А.   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

Петя считает, что у каждой банки есть нестабильность, и если эта характеристика больше m, то банка падает.

Петя придумал стратегию расстановки: если ставить одну банку прямо на предыдущую, то ее нестабильность рассчитывается как нестабильность нижестоящей, умноженная на k2.

А если ставить банки пирамидой, то есть каждую следующую ставить на две предыдущие, то нестабильность рассчитывается как нестабильность нижестоящей, умноженная на k.

Если поставить банку на пол, то ее нестабильность равна единице.

Требуется узнать, башню какой максимальной высоты может построить Петя.

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

Входной файл содержит три целых числа N, k и m.

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

Выходной файл должен содержать единственное целое число - высоту башни.

Ограничения

0 < N ≤ 109

1 < k ≤ 104

1 < m ≤ 109

Описание системы оценивания

Подзадача Ограничения Баллы
1 N, k, m < 5010
2 N, k, m < 2 * 10320
3 N, k, m < 2 * 10420
4 N, k, m < 2 * 10520
5 N, k, m < 2 * 10610
6 нет 20

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

Стандартный вход Стандартный выход
1
4 2 9
3
2
13 3 100000
7

0.230s 0.021s 17