Description

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}$).

Input Format

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

Output Format

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

10 3 3

2

Hint

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