C. Жадный Аркадий
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

$$$k$$$ людей хотят разделить $$$n$$$ конфет между собой. Каждая конфета должна достаться ровно одному из этих людей либо быть выброшена.

Люди пронумерованы от $$$1$$$ до $$$k$$$, и Аркадий — первый из них. Чтобы разделить конфеты, Аркадий выберет целое положительное число $$$x$$$, после чего заберет первые $$$x$$$ конфет себе, следующие $$$x$$$ конфет отдаст второму человеку, следующие $$$x$$$ конфет — третьему человеку и так далее по кругу. Остаток (от деления числа конфет на $$$x$$$) будет выброшен.

Аркадий не может выбрать $$$x$$$ больший, чем $$$M$$$, так как это будет расценено как слишком жадное поведение. Также он не может выбрать настолько малый $$$x$$$, что кто-то получит конфеты больше $$$D$$$ раз, так как такое разделение посчитают слишком медленным.

Пожалуйста, найдите максимальное количество конфет, которое может получить Аркадий при раздаче с корректным $$$x$$$.

Входные данные

В единственной строке содержится четыре целых числа $$$n$$$, $$$k$$$, $$$M$$$ и $$$D$$$ ($$$2 \le n \le 10^{18}$$$, $$$2 \le k \le n$$$, $$$1 \le M \le n$$$, $$$1 \le D \le \min{(n, 1000)}$$$, $$$M \cdot D \cdot k \ge n$$$) — число конфет, число людей, максимальное число конфет, отпускаемое за раз в одни руки и максимальное количество раз, которое один человек может получать конфеты.

Выходные данные

Выведите одно целое число — максимальное количество конфет, которое Аркадий может отдать самому себе.

Обратите внимание, выбрать хотя бы один корректный $$$x$$$ всегда возможно.

Примеры
Входные данные
20 4 5 2
Выходные данные
8
Входные данные
30 9 4 1
Выходные данные
4
Примечание

В первом примере Аркадий должен выбрать $$$x = 4$$$. Он отдаст $$$4$$$ конфеты себе, $$$4$$$ конфеты второму, $$$4$$$ конфеты третьему, после чего $$$4$$$ четвёртому и опять $$$4$$$ конфеты себе. Никто не получал конфет больше $$$2$$$ раз и Аркадий получит в общей сложности $$$8$$$ конфет.

Заметьте, что если Аркадий выберет $$$x = 5$$$, он получит только $$$5$$$ конфет, и если он выберет $$$x = 3$$$, он получит только $$$3 + 3 = 6$$$ конфет, как и второй, третий и четверный получат по $$$3$$$ конфеты, а $$$2$$$ конфеты будут выброшены. Он не может выбрать $$$x = 1$$$, как и $$$x = 2$$$, потому что в этом случае он получит конфеты больше $$$2$$$ раз.

Во втором примере Аркадий обязан выбрать $$$x = 4$$$, так как любое значение меньше приведёт к тому, что он получит конфеты больше $$$1$$$ раза.