Farmer John's Milk Repayment

Farmer John owes Bessie \(N\) gallons of milk and must repay at least \(N\) gallons within \(K\) days. However, he does not want to pay too soon, so he postpones the payments as long as possible. To do so, he chooses a positive integer \(X\) and follows the process below every day:

1. Let \(G\) be the total milk given so far. Compute \(Y = \left\lfloor \frac{N-G}{X} \right\rfloor\).
2. If \(Y < M\), then set \(Y = M\).
3. Give Bessie \(Y\) gallons of milk.

It is guaranteed that with \(X=1\) the process will repay at least \(N\) gallons in \(K\) days. Find the maximum value of \(X\) (a positive integer) such that following the above process, Farmer John repays at least \(N\) gallons of milk after \(K\) days.

The parameters satisfy the constraints:

• \(1 \leq N \leq 10^{12}\)
• \(1 \leq M \leq 10^{12}\)
• \(1 \leq K \leq 10^{12}\)

Note: It is assumed that the debt is so large that repaying exactly \(K \times M\) gallons (i.e. paying only the minimum \(M\) each day) is not enough, ensuring a unique maximum \(X\) exists.

inputFormat

The input consists of a single line containing three space-separated integers: \(N\), \(M\), and \(K\).

\(N\): total gallons of milk owed.
\(M\): minimum gallons to be paid each day.
\(K\): number of days available for repayment.

outputFormat

Output a single integer, the maximum possible value of \(X\) such that following the process, at least \(N\) gallons are repaid in \(K\) days.

sample

100 3 10

3