Задача B. Наилучшее обучение

Автор:М. Панов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

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

Формат входного файла

Первая строка входного файла содержит три целых числа a, n и b, разделенные пробелами.

Формат выходного файла

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

Ограничения

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

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

Подзадача Баллы Ограничения
anb
1601 ≤ a ≤ 1031 ≤ n ≤ 1031 ≤ b ≤ 109
2401 ≤ a ≤ 1061 ≤ n ≤ 1091 ≤ b ≤ 1018

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5 10 15
3
2
10 10 10
1

0.072s 0.014s 13