题目描述

小 $\mathrm{W}$ 因为模拟赛做自闭了，于是出来散步（否则他就只能在机房看知乎)。

小 $\mathrm{W}$ 找到了一个售货机，这个售货机只收津巴布韦币，并且只收 $1$ 元 和 $10^{6}$ 元两种面值的津巴布韦币。

小 $\mathrm{W}$ 看到售货机上有卖脉动，于是想买一瓶㡫。一瓶脉动的价格是 $r$ 津巴布韦币。当然, 由于小 $\mathrm{W}$ 贪得无厌，他想要尽量多的购买脉动。 他摸了摸口袋, 发现他只有 $b$ 张 $10^{6}$ 元纸币和 $c$ 个 $1$ 元硬币，同时, 他看到售货机显示售货机里还存在 $d$ 个 1 元硬币用于找零。

他知道这个售货机会按照一下规则找零：

1. 假设收下 $x$ 张 $10^{6}$ 元纸币和 $y$ 个 1 元硬币，如果 $10^{6} \times x+y<r$, 售 货机当然不会卖给你水，并且将会把这些钱全部退回。

2. 售货机会尝试用售货机里的银币进行找零，如果不能成功找零，售货机将会把这些钱全部退回。

3. 如果能够找零，则售货机会先收下这些钱（其中收下的硬币可以用于下次找零）。然后会支付给顾客找零（全部以硬币形式)。

然而因为这个售货机比较老旧，他只能够一瓶一瓶的买。 现在小 $\mathrm{W}$ 想知道他最多能买多少瓶脉动，你能帮帮他吗?

输入格式

第一行两个整数 $b, c$, 表示小 $\mathrm{W}$ 当前拥有的钱。

第二行两个整数 $r, d$, 表示脉动的价格和售货机当前的银币。

输出格式

输出一行一个整数表示答案。

样例

21 1000000
1100000 0

20

10 700000
350000 200000

4

子任务

subtask $1$ $(30 \mathrm{pts})$: $0 \leq b \leq 10,0 \leq c, d \leq 10^{6}, 1 \leq r \leq 10^{9}$。

subtask $2$ $(70 \mathrm{pts})$：$0 \leq b, c, d \leq 10^{9}, 1 \leq r \leq 10^{9}$。