问题 5080 --吃席

5080: 吃席★★★★

时间限制: 1 Sec  内存限制: 256 MB
提交: 63  解决: 33
[提交][状态][命题人:]

题目描述

小明请大家吃席。
共有 k 个人参加宴会,宴会上有 n 份点心。每份点心只能分给某个人或被放弃。每个人都有个序号,小明是 1 号。
分配点心的方式为:每轮按顺序从剩余点心中选取 x 份点心给 1 号,再选 x 份点心给 2号,再选 x 份点心给 3号...... 直到最后选 x 份点心给 k 号。若还有剩余点心,则开启下一轮的分配。如果分配到某个人时,剩余点心数量不足 x 个,则放弃剩余所有点心,结束分配。
为了使得分配过程“尽可能”公平和快捷,需满足 x 不超过 M ,且不会有人被分配超过 D 次。
求 x 取值合法的情况下,小明最多可以获得多少点心。

输入

输入包含四个整数 n,k,M,D(2≤n≤10^18, 2≤k≤n, 1≤M≤n, 1≤D≤min(n,1000)) 。

输出

输出一个整数,表示小明最多可以获得的点心数。
样例输入
Copy
20 4 5 2
样例输出
Copy
8

提示

样例2输入
30 9 4 1

样例2输出
4

在样例1中,可以选择 x=4 。
在样例2中,可以选择 x=4 。

来源

[提交][状态]