Problem D
Duck Division
Dorothea’s duck flock is getting a bit out of hand! The flock is now so big that it’s very hard to handle them all, and getting them into the duck pen for the night takes almost the entire evening.
That’s a problem, because Dorothea wants to watch the new series “Quacka” before going to bed. Now she doesn’t have enough time to do that! However, she knows that herding a flock of $D$ ducks into a duck pen take $\Theta (D^2)$ time. For that reason, she wants to temporarily split her flock into smaller divisions to make them easier to herd. They will all have their separate locations in her backyard, so there’s no possibility of them mixing up and making it hard to herd them the following evening.
But ducks are very social animals, and a flock of ducks will be sad if there are fewer than $U$ ducks in the flock. Dorothea wants to ensure that none of her ducks are sad. Additionally, Dorothea doesn’t want to remember a lot of numbers, so the divisions must all be of the same size: This makes it much easier to check that none of the ducks have gone missing during the night.
Dorothea wonders if you could help her find the smallest size of a duck division that satisfies these criteria.
Input
The input is a single line with two integers, $D$ and $U$, the number of ducks in Dorothea’s flock, and the minimal number of ducks that should be in a division.
Output
Output the lowest acceptable size of a duck division.
Limits
-
$0 < U \leq D \leq 10^{12}$
| Sample Input 1 | Sample Output 1 |
|---|---|
14 5 |
7 |
| Sample Input 2 | Sample Output 2 |
|---|---|
114 10 |
19 |
| Sample Input 3 | Sample Output 3 |
|---|---|
31 5 |
31 |
