Greedy Arkady

The people are numbered from $1$ to $k$ , and Arkady is the first of them. To split the candies, Arkady will choose an integer $x$ and then give the first $x$ candies to himself, the next $x$ candies to the second person, the next $x$ candies to the third person and so on in a cycle. The leftover (the remainder that is not divisible by $x$ ) will be thrown away.

Arkady can't choose $x$ greater than $M$ as it is considered greedy. Also, he can't choose such a small $x$ that some person will receive candies more than $D$ times, as it is considered a slow splitting.

Please find what is the maximum number of candies Arkady can receive by choosing some valid $x$ .

Input

The only line contains four integers $n$ , $k$ , $M$ and $D$ ( $2 \leq n \leq 10^{18}$ , $2 \leq k \leq n$ , $1 \leq M \leq n$ , $1 \leq D \leq min (n, 1000)$ , $M \cdot D \cdot k \geq n$ ) — the number of candies, the number of people, the maximum number of candies given to a person at once, the maximum number of times a person can receive candies.

Output

Print a single integer — the maximum possible number of candies Arkady can give to himself.

Note that it is always possible to choose some valid $x$ .

Examples

Input

20 4 5 2

Output

Input

30 9 4 1

Output

4


Solution

#include <bits/stdc++.h>

using namespace std;

int main() {

long long n, k, M, D;

cin >> n >> k >> M >> D;

if (n <= M) {

cout << n << endl;

return 0;

}

long long low, mid, high;

low = n / (k * D);

high = M;

mid = (low + high) / 2;

while (low != high) {

mid = (low + high) / 2;

if (mid > low) {

low = mid;

} else {

high = mid;

}

cout << mid * D << endl;

return 0;

}

Comments