You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

除了毛绒玩具之外，Imp 还是小黄鸟的超级粉丝！

为了召唤小鸟，Imp 需要强大的魔法。在公园的一条小路上有 $n$ 棵树排成一行，每棵树上都有一个鸟巢。在第 $i$ 个鸟巢中有 $c_i$ 只鸟；Imp 要从这个鸟巢召唤一只鸟，需要在这棵树下停留，并消耗 $cost_i$ 点魔力。然而，每召唤一只鸟，Imp 的魔力上限会增加 $B$ 点。Imp 可以一只一只地召唤小鸟，他可以从第 $i$ 个鸟巢中召唤 $0$ 到 $c_i$ 只鸟。

最开始，Imp 站在第一棵树下，拥有 $W$ 点魔力，魔力上限也是 $W$。他只能向前走，每次从一棵树走到下一棵树时，会恢复 $X$ 点魔力（但不会超过当前的魔力上限）。只能向前移动，Imp 最多能召唤多少只小鸟？

输入格式

第一行包含四个整数 $n$、$W$、$B$、$X$（$1 \leq n \leq 10^3, 0 \leq W,B,X \leq 10^9$），分别表示树的数量、初始魔力值、每召唤一只鸟魔力上限增加的值，以及每次移动恢复的魔力值。

第二行包含 $n$ 个整数 $c_1, c_2, ..., c_n$（$0 \leq c_i \leq 10^4$），其中 $c_i$ 表示第 $i$ 个鸟巢中的小鸟数量。保证 $\sum c_i \leq 10^4$。

第三行包含 $n$ 个整数 $cost_1, cost_2, ..., cost_n$（$0 \leq cost_i \leq 10^9$），其中 $cost_i$ 表示从第 $i$ 个鸟巢召唤一只鸟所需的魔力值。

输出格式

输出一个整数，表示 Imp 最多能召唤的小鸟数量。

2 12 0 4
3 4
4 2

6

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

5

2 10 7 11
2 10
6 1

11

说明/提示

在第一个样例中，Imp 的基础魔力为 $12$（最大上限也是 $12$）。他从第一个鸟巢召唤两只鸟，消耗 $8$ 点魔力，但由于 $B=0$，魔力上限不会增加。此时魔力为 $4/12$；移动时恢复 $4$ 点魔力，因此拥有 $8/12$ 的魔力。此时最优选择是从第二个鸟巢召唤 $4$ 只鸟，消耗 $8$ 点魔力。最终答案为 $6$。

在第二个样例中，基础魔力为 $1000$。最优选择是直接从最后一个鸟巢召唤所有小鸟。注意，由于初始魔力已满，移动时魔力不会恢复。