描述

你是一名猫咪魔法师，现在想要召唤猫咪。

有一条路，路上有 n 棵树，每颗树上有 \({c_i}\) 只猫咪。你在树底下可以花费 \({cost_i}\) 点蓝量召唤一直猫咪，每召唤一只猫咪，你的蓝量上限增加 B（不增加蓝量），从一颗树走到下一棵树，你会回复 X 点蓝量。你的初始蓝量和上限都是 W ，你的蓝量不能超过上限，你只能从第一棵树开始走。

你能最多召唤多少只猫咪？

输入

第一行包含四个整数 n，W，B，X（1≤n≤\({10^3}\)，0≤W，B，X≤\({10^9}\)）—树的数量，法力的初始点，召唤一只猫咪之后法力上限增加的点数，当从一棵树移到下一棵树时，蓝量恢复的数量。

第二行包含 n 个整数\({ c_1，c_2，...，c_n（0≤c_i≤10^4}\)）其中 c_i 是生活在第 ii个树中的猫咪的数量。 可以保证 \({∑^n_i c_i <= 10^4}\)

第三行包含 n 个整数，分别为\({cost_1，cost_2，...，cost_n（0≤cost_i≤10^9）}\)其中&{cost_i}$是从第 i 个树召唤一只猫咪的法力消耗。

输出

输出一个整数--你所能召唤最大的猫咪数量。

样例

2 12 0 4
3 4
4 2

6

5 1 4 6
3 4 6 5 1
3 0 10 2 9

10

提示

【样例解释】

在第一棵树召唤两只猫咪，剩余法力值4点，走到下棵树，法力值为8点，召唤4只猫咪，总共6只猫咪。

【数据说明】

对于20%的数据： \({1 \le n \le 101≤n≤10 }\)

对于60%的数据： \({1 \le n \le 1001≤n≤100 }\)

对于100%的数据： \({1 \le n \le 10001≤n≤1000 }\)

题解

CODE

AC代码

C - 召唤猫咪

原文：https://www.cnblogs.com/Little-Turtle--QJY/p/13887323.html