Loan Repayment
Farmer John owes Bessie n gallons of milk. He has to give her the milk within k days. However, he doesn't want to give the milk away too quickly. On the other hand, he has to make forward progress on the loan, so he must give Bessie at least m gallons of milk each day.
Here is how Farmer John decides to pay back Bessie. He first picks a positive integer x. He then repeats the following procedure every day:
Assuming that Farmer John has already given Bessie g gallons, compute (n − g) / x rounded down. Call this number y.
If y is less than m, set y to m.
Give Bessie y gallons of milk.
Determine the largest x such that if Farmer John follows the above procedure, Farmer John gives Bessie at least n gallons of milk after k days.
Input
Three positive integers n (1 ≤ n ≤ 10^12), k (1 ≤ k ≤ 10^12), m (1 ≤ m ≤ 10^12), satisfying k * m < n.
Output
Output the largest positive integer x such that Farmer John will give Bessie at least n gallons using the above procedure.
Example
For the first test case, when x = 2 Farmer John gives Bessie 5 gallons on the first day and m = 3 gallons on each of the next two days.