← 返回题目列表

Codeforces · 965/C

C. 贪婪的阿尔卡迪

中文机器翻译题面 查看原题

$$$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$$$ 时间。