Фермер Джон должен Беси \(N\) галлонов молока (\(1\le N\le 10^{12}\)).
Он должен вернуть ей молоко в течение \(K\) дней. Однако он не хочет
отдавать молоко слишком быстро. С другой стороны, он должен показывать
прогресс в возвращении долга. Поэтому он должен возвращать Беси не менее
\(M\) галлонов молока (\(1\le M\le 10^{12}\)) каждый день.
ФД собирается делать так.
Он выбирает положительное целое число \(X\).
А затем повторяет следующую процедуру каждый день:
- Предположим, что ФД уже отдал Беси \(G\) галлонов молока,
он вычисляет \(\frac{N-G}{X}\) с округлением вверх. Назовём это число \(Y\).
- Если \(Y\) меньше чем \(M\), то устанавливает \(Y\) равным \(M\).
- Даёт Беси \(Y\) галлонов молока.
Определите максимальное \(X\) такое, что если ФД будет следовать этой процедуре,
то ФД отдаст Беси не менее \(N\) галлонов молока после \(K\) дней (\(1\le K\le 10^{12}\)).
ОЦЕНИВАНИЕ:
- Тесты 2-4 удовлетворяют ограничению \(K\le 10^5.\)
- Тесты 5-11 не имеют дополнительных ограничений.
ФОРМАТ ВВОДА (файл loan.in):
Единственная строка ввода содержит три разделённых пробелом целых положительных
числа \(N\), \(K\), \(M\) удовлетворяющих \(K\cdot M<N\).
ФОРМАТ ВЫВОДА (файл loan.out):
Выведите наибольшее положительное целое число \(X\) такое, что ФД отдаст Беси
не менее \(N\) галлонов молока используя описанную выше процедуру.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 3 3
|
2
|