Greedy Arkady

k명의 사람이 n개의 사탕을 나누어 가지려고 한다. 각 사탕은 정확히 한 사람에게 주거나 버려야 한다.

사람들에게 1부터 k까지 번호가 매겨져 있으며, Arkady는 그중 첫 번째 사람이다. 사탕을 나누기 위해 Arkady는 정수 x를 선택한 뒤, 처음 x개의 사탕을 자신에게 주고, 다음 x개의 사탕을 두 번째 사람에게 주며, 다음 x개의 사탕을 세 번째 사람에게 주는 식으로 이 과정을 순환해서 반복한다. 남은 사탕(x로 나누어떨어지지 않는 나머지)은 버린다.

x가 M보다 크면 탐욕스럽다고 여겨지므로 Arkady는 그런 값을 선택할 수 없다. 또한 어떤 사람이 사탕을 D번보다 많이 받게 될 정도로 작은 x도 선택할 수 없다. 이는 사탕을 나누는 과정이 느리다고 여겨지기 때문이다.

Arkady가 유효한 x를 선택하여 받을 수 있는 사탕의 최대 개수를 구하라.

유일한 줄에 네 정수 n, k, M and D (2 ≤ n ≤ $10^{18}$, 2 ≤ k ≤ n, 1 ≤ M ≤ n, 1 ≤ D ≤ min{(n, 1000)}, M ⋅ D ⋅ k ≥ n)가 주어진다. 각각 사탕의 개수, 사람의 수, 한 번에 한 사람에게 주는 사탕 개수의 최댓값, 한 사람이 사탕을 받을 수 있는 횟수의 최댓값을 나타낸다.

Arkady가 자신에게 줄 수 있는 사탕 개수의 가능한 최댓값을 나타내는 정수 하나를 출력한다.

유효한 x를 항상 선택할 수 있음에 유의하라.

첫 번째 예제에서 Arkady는 x = 4를 선택해야 한다. 그는 자신에게 사탕 4개를 주고, 두 번째 사람에게 사탕 4개를 주고, 세 번째 사람에게 사탕 4개를 준 다음, 네 번째 사람에게 사탕 4개를 주고 다시 자신에게 사탕 4개를 준다. 어느 사람도 사탕을 2번보다 많이 받지 않으며, Arkady는 총 8개의 사탕을 받는다.

Arkady가 x = 5를 선택하면 사탕을 5개만 받으며, x = 3을 선택하면 3 + 3 = 6개의 사탕만 받는다는 점에 유의하라. 또한 두 번째 사람, 세 번째 사람, 네 번째 사람은 사탕을 3개씩 받고 사탕 2개는 버려진다. x = 1이나 x = 2는 선택할 수 없다. 이 경우에는 사탕을 2번보다 많이 받게 되기 때문이다.

두 번째 예제에서 Arkady는 x = 4를 선택해야 한다. 이보다 작은 값을 선택하면 모두 사탕을 1번보다 많이 받게 되기 때문이다.