\(k\) людей хотят разделить \(n\) конфет между собой. Каждая конфета должна достаться ровно одному из этих людей либо быть выброшена.
Люди пронумерованы от \(1\) до \(k\), и Аркадий — первый из них. Чтобы разделить конфеты, Аркадий выберет целое положительное число \(x\), после чего заберет первые \(x\) конфет себе, следующие \(x\) конфет отдаст второму человеку, следующие \(x\) конфет — третьему человеку и так далее по кругу. Остаток (от деления числа конфет на \(x\)) будет выброшен.
Аркадий не может выбрать \(x\) больший, чем \(M\), так как это будет расценено как слишком жадное поведение. Также он не может выбрать настолько малый \(x\), что кто-то получит конфеты больше \(D\) раз, так как такое разделение посчитают слишком медленным.
Пожалуйста, найдите максимальное количество конфет, которое может получить Аркадий при раздаче с корректным \(x\).
Выходные данные
Выведите одно целое число — максимальное количество конфет, которое Аркадий может отдать самому себе.
Обратите внимание, выбрать хотя бы один корректный \(x\) всегда возможно.
Примечание
В первом примере Аркадий должен выбрать \(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\) раза.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
20 4 5 2
|
8
|
|
2
|
30 9 4 1
|
4
|