P6003 [USACO20JAN] Loan Repayment S

Farmer John owes Bessie $N$ gallons of milk ($1 \leq N \leq 10^{12}$). He must give the milk to Bessie within $K$ days. However, he does not want to hand over the milk too early. On the other hand, he has to make progress on repaying the debt, so he must give Bessie at least $M$ gallons of milk every day ($1 \leq M \leq 10^{12}$). Here is how Farmer John decides to repay Bessie. First, he chooses a positive integer $X$. Then, every day he repeats the following process: 1. Suppose Farmer John has already given Bessie $G$ gallons. Compute $\left\lfloor \frac{N - G}{X} \right\rfloor$. Let this number be $Y$. 2. If $Y$ is less than $M$, set $Y$ to $M$. 3. Give Bessie $Y$ gallons of milk. Find the maximum value of $X$ such that Farmer John can give Bessie at least $N$ gallons of milk after $K$ days by following the process above ($1 \leq K \leq 10^{12}$).

The input contains only one line with three space-separated positive integers $N, K, M$, satisfying $K \times M < N$.

Output the largest positive integer $X$ such that, following the process above, Farmer John will give Bessie at least $N$ gallons of milk.

### Sample Explanation In this test case, when $X = 2$, Farmer John gives Bessie $5$ gallons on the first day, and then gives $M = 3$ gallons on each of the next two days. ### Subtasks - Test points $2 \sim 4$ satisfy $K \leq 10^5$. - Test points $5 \sim 11$ have no additional constraints. Translated by ChatGPT 5