Migrated from Lutece 2038 希望与你共进晚餐

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

在子辉不断的“挑战”的过程中，Sakura 也发觉了 子辉 确实智商过人，同时在收到了那封情书后也了解到了子辉对自己的情感。但却并没有直接接受子辉的告白， 而只是表示再让自己考虑考虑， 子辉 觉得还需要再加点火候，便邀请 Sakura 共进自助晚餐。

在这次自助餐中，服务员将会依次推送 $n$ 种食物，第 $i$ 种食物总共有 $a_i$ 份，子辉 可以拿取若干份进行享用，然后服务员就会离开准备下一道菜肴。众所周知，和妹子吃饭是一种极其消耗脑力的博弈活动，子辉 在进餐的同时还要与Sakura谈笑风声，所以每吃完一份第 $i$ 种食物会消耗 $b_i$ 点脑力，同时心情大悦，会暂时性地激发额外 $X$ 点智商，而每推送来一种食物 (第一种食物不算) ，子辉便会增加 $Y$ 单位的脑力（不论吃没吃）（但是脑力不能超过智商，即脑力值永远小于等于智商值）。

子辉 一开始有 $V$ 点智商和 $V$ 点脑力，现在他想知道在保证脑力一直处于非负状态能够展现个人魅力的同时，他最多能吃多少份食物。

Input

第一行 4 个整数，$n,V,X,Y$。$1\leq n\leq 200,0\leq V,X,Y \leq 10^9$ 第二行 $n$ 个数，第 $i$ 个数代表 $a_i$。$0\leq a_i \leq 10^5, \sum_{i=1}^{n}a_i\leq 10^5$ 第三行 $n$ 个数，第 $i$ 个数代表 $b_i$。$0\leq b_i\leq 10^9$

Output

一个整数，代表最多能吃的食物的总份数。

Samples

3 10 2 3
3 5 4
3 2 1

9

3 10 2 16
6 10 8
3 2 1

19

Note

第二个样例：一开始脑力和智力为 $(10, 10)$。 吃 3 份食物 ①，$(10 - 3b_1 + Y, 10 + 3X) = (17, 16)=>(16,16)$ 吃 8 份食物 ②，$(16 - 8b_2 + Y, 16 + 8X) = (16, 32)$ 吃 8 份食物 ③，$(16 - 8b_3 + Y, 32 + 8X) = (24, 48)$

Resources

2018 UESTC Training for Dynamic Programming