$$$k$$$ 人们想要在他们之间分配 $$$n$$$ 糖果。每颗糖果都应该只给其中一个人,否则就被扔掉。
人员编号从 $$$1$$$ 到 $$$k$$$,Arkady 是其中的第一位。为了分割糖果,Arkady 会选择一个整数 $$$x$$$,然后将第一个 $$$x$$$ 糖果给自己,将下一个 $$$x$$$ 糖果给第二个人,将下一个 $$$x$$$ 糖果给第三个人,如此循环。剩下的(不能被 $$$x$$$ 整除的余数)将被扔掉。
Arkady 无法选择大于 $$$M$$$ 的 $$$x$$$,因为它被认为是贪婪的。另外,他不能选择这么小的$$$x$$$,以至于有些人会收到超过$$$D$$$次的糖果,因为这被认为是一种缓慢的分裂。
请通过选择一些有效的$$$x$$$来找出Arkady最多可以收到多少糖果。
输入
唯一一行包含四个整数 $$$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$$$) — 糖果数量、人数、一次给一个人的最大糖果数量、一个人可以收到糖果的最大次数。
输出
打印一个整数——Arkady 可以给自己的最大可能糖果数量。
请注意,始终可以选择一些有效的 $$$x$$$。
示例
输入 #1
20 4 5 2
输出 #1
8
输入 #2
30 9 4 1
输出 #2
4
注意
在第一个示例中,Arkady 应选择 $$$x = 4$$$。他会给自己 $$$4$$$ 糖果,给第二个人 $$$4$$$ 糖果,给第三个人 $$$4$$$ 糖果,然后给第四个人 $$$4$$$ 糖果,然后再给自己 $$$4$$$ 糖果。没有人获得的糖果超过 $$$2$$$ 次,阿尔卡迪总共收到 $$$8$$$ 糖果。
注意,如果Arkady选择$$$x = 5$$$,他只会收到$$$5$$$糖果,如果他选择$$$x = 3$$$,他只会收到$$$3 + 3 = 6$$$糖果,第二人、第三和第四人将收到$$$3$$$糖果,并且会扔出$$$2$$$糖果离开。他不能选择 $$$x = 1$$$ 也不能选择 $$$x = 2$$$,因为在这些情况下,他收到糖果的次数将超过 $$$2$$$ 次。
在第二个例子中,Arkady 必须选择 $$$x = 4$$$,因为任何较小的值都会导致他收到糖果的时间超过 $$$1$$$ 时间。