题目描述

现在要给 $k$ 个人分掉 $n$ 块糖。每块糖要么分给某个人，要么被扔掉(不会有掰一半的情况)。初步设想的分糖策略是这样的:

先给参加分糖的 $k$ 个人按从 $1$ 到 $k$ 的次序编上号，小 A 的序号是 $1$ 。首先，小 A 从所有的糖果中拿出 $x$ 块给自己，接着拿出 $x$ 块给编号为 2 的人，....，当给完最后一个人后，如果还有足够的糖果这个过程会再次从 $1$ 号开始。如果到某个人的时候，剩余的糖果不够 $x$ 个，那么就扔掉剩余的糖果。小 A 不会选择一个大于 $M$ 的数作为 $x$，也不会选择一个过小的以至于某个人被分糖的次数超过了 $D$ ，也不会选择一个过小的 $x$ 以至于某个人被分糖的次数超过了 $D$ (这样会让大家觉得太繁琐了)。

请问：小 A 通过选择一个合适的 $x$ ，最多能让自己得到多少糖果？

输入格式

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

数据范围

对于所有数据：$1 <= D <= min(n,1000)$ , $M \times D \times k \ge n$ ;

对于 50% 的数据，$2 \le n \lt 10^9$ , $2 \le k \le min(n,10^6)$ , $1 \le M \le n$ ;

对于另外 50% 的数据： $2 \lt n \lt 10^{18}$ , $2 \le k \le n$ ; $1 \le M \le n$ 。

输出格式

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

样例

20 4 5 2

8

30 9 4 1

4

样例解释

第一个例子中，小 A 应该选择 x=4，他会给自己 4 块糖，分别给第二、三、四个人 4 块糖，最后再给自 4 块糖。没有人被给了超过 2 次糖，小 A 最终收到 8 块糖。如果小 A 选择 x=5 他只会收到 5 块糖；如果小 A 选择 x=3，他会收到 3+3=6 块糖，与第二个人一样;第三个人会收到 3 块糖，最后 2 块糖会被扔掉。他不能选择 x=1 或 x=2 因为这样会导致他收到糖的次数大于 2 。

第二个例子中小 A 必须选择 x=4，因为任何小于 4 的值都会导致他少分到糖。