U213538 分糖果(candy) [2021年9月海淀区赛小学组T4]

2021年9月海淀区赛小学组T4

现在要给k个人分掉n块糖。每块糖要么分给某个人，要么被扔掉（不会有掰一半的情况）。初步设想的分糖策略是这样的： 先给参加分糖的k个人按从1到k的次序编上号，小A的序号是1。首先，小A从所有的糖果中x块给自己，接着拿出x块给编号为2的人，......，当给完最后一个人后，如果还有足够的糖果，这个过程会再次从1号开始。如果到某个人的时候，剩余的糖果不够x个，那么就扔掉剩余的糖果。小A不会选择一个大于M的数作为x，也不会选择一个过小的x以至于某个人被分糖的次数超过了D（这样会让大家觉得太繁琐了）。 请问：小A通过选择一个合适的x,最多能让自己得到多少糖果？

仅有一行，包含4个整数n,k,M,D，含义如题目所述。

一行，仅有一个整数，表示题目要求的结果。

对于所有数据：1≤D≤min(n,1000),M$\times$D$\times$k≥n； 对于50%的数据，2≤n≤$10^9$，2≤k≤min(n, $10^9$),1≤M≤n； 对于另外50%的数据：2≤n≤$10^1$$^8$，2≤k≤n，1≤M≤n。 **样例解释：** 第一个例子中，小A应该选择x=4，他会给自己4块糖，分别给第二、三、四个人4块糖，最后再给自己4块糖，小A最终收到8块糖。如果小A选择x=5，他只会收到5块糖；如果小A选择x=3，他会收到3+3=6块糖，与第二个人一样；第三个人会收到3块糖，最后2块糖会被扔掉。他不选择x=1或x=2，因为这样会导致他收到糖的次数大于2。 第二个例子中，小A必须选择x=4，因为任何小于4的值都会导致他少收获糖。