Loan Repayment#9600
Farmer John owes Bessie gallons of milk. He must give her all of the milk within days. However, he does not want to give the milk away too quickly. On the other hand, he needs to make steady progress on the loan, so he must give Bessie at least gallons of milk each day.
Here is how Farmer John decides to repay Bessie. First, he chooses a positive integer . Then, each day, he repeats the following procedure:
Suppose Farmer John has already given Bessie gallons of milk. He computes (n-g)/x, rounded up, and calls the result .
If is less than , he sets y = m.
He gives Bessie gallons of milk.
Determine the largest value of such that, after days, Farmer John has given Bessie at least gallons of milk when following the procedure above.
Consists of three positive integers , and m~(1 \le n, k, m \le 10^{12}), satisfying k \cdot m < n.
Print the largest positive integer such that Farmer John gives Bessie at least gallons of milk after days when following the procedure above.
For the first test case, when x = 2, Farmer John gives Bessie gallons on the first day and gallons (which equals ) on each of the next two days.
Example 1