e-olymp
Задачи

Возврат кредита

Возврат кредита

Фермер Джон должен Бесси n галлонов молока. Он должен вернуть ей молоко в течение k дней. Однако он не хочет отдавать молоко слишком быстро. С другой стороны, он должен показывать прогресс в возвращении долга. Поэтому он должен возвращать Бесси не менее m галлонов молока каждый день.

ФД собирается делать так. Он выбирает положительное целое число x. Затем повторяет следующую процедуру каждый день:

  • Предположим, что ФД уже отдал Бесси g галлонов молока, он вычисляет (ng) / x с округлением вверх. Назовём это число y.
  • Если y меньше чем m, то устанавливает y равным m.
  • Даёт Бесси y галлонов молока.

Определите максимальное x такое, что если ФД будет следовать этой процедуре, то ФД отдаст Бесси не менее n галлонов молока после k дней.

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

Три натуральных числа n (1n1012), k (1k1012), m (1m1012), удовлетворяющих k * m < n.

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

Выведите наибольшее натуральное число x такое, что ФД отдаст Бесси не менее n галлонов молока, используя описанную выше процедуру.

Пример

Для первого теста, когда x = 2, ФД отдаст Бесси 5 галлонов молока в первый день и m = 3 галлонов молока в каждый из двух последующих дней.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
10 3 3
Выходные данные #1
2
Источник 2020 USACO January Silver