← 返回题目列表

Codeforces · 922/E

E. 鸟类

中文机器翻译题面 查看原题

除了毛绒玩具,小鬼还是小黄鸟的超级粉丝!

为了召唤鸟类,小鬼需要强大的魔法。公园的一条小巷里有一排n棵树,每棵树上都有一个鸟巢。第i个巢中有ci鸟;要从这个巢中召唤一只鸟,小鬼需要呆在这棵树下,这会花费他大量的法力值。然而,每召唤一只鸟,Imp 就会增加 B 点法力值。小鬼一只一只地召唤小鸟,他可以从第i个巢穴中召唤0到ci中任意数量的小鸟。

最初小鬼站在第一棵树下,拥有W点法力,他的法力容量也等于W。他只能前进,每次从一棵树移动到下一棵树时,他都会恢复X点法力(但不能超过他当前的法力容量)。只向前看,Imp 最多可以召唤多少只鸟?

输入

第一行包含四个整数 n, W, B, X (1 ≤ n ≤ 103, 0 ≤ W, B, X ≤ 109)——树的数量,初始法力点,召唤小鸟后法力容量增加的点数,以及 Imp 从一棵树移动到下一棵树时恢复的点数。

第二行包含 n 个整数 c1, c2, ..., cn (0 ≤ ci ≤ 104) - 其中 ci 是生活在第 i 个巢中的鸟的数量。保证 $$\sum_{i=1}^{n} c_i \leq 10^4$$。

第三行包含 n 个整数 cost1, cost2, ..., costn (0 ≤ costi ≤ 109),其中 costi 是从第 i 个巢中召唤小鸟的法力消耗。

输出

打印一个整数——小鬼可以召唤的最大鸟类数量。

示例

输入 #1

2 12 0 4
3 4
4 2

输出 #1

6

输入 #2

4 1000 10 35
1 2 4 5
1000 500 250 200

输出 #2

5

输入 #3

2 10 7 11
2 10
6 1

输出 #3

11

注意

在第一个样本中,Imp 的法力基础量等于 12(最大容量也等于 12)。当他从第一个巢中召唤两只鸟后,他会失去 8 点法力值,但他的最大容量不会增加(因为 B = 0)。在此步骤之后,他的法力值将变为 12 点中的 4 点;在移动过程中,您将补充 4 点法力值,因此拥有 12 点法力值中的 8 点。现在最好从第二个巢中拿走 4 只鸟并花费 8 点法力。最终答案是——6。

在第二个示例中,法力的基础量等于 1000。正确的选择是简单地从最后一个巢中拾取所有鸟类。请注意,小鬼的法力在移动时不会恢复,因为它最初已满。