English · Original
Chinese · Translation
Formal · Original
Apart from plush toys, Imp is a huge fan of little yellow birds!
<center></center>To summon birds, Imp needs strong magic. There are _n_ trees in a row on an alley in a park, there is a nest on each of the trees. In the _i_\-th nest there are _c__i_ birds; to summon one bird from this nest Imp needs to stay under this tree and it costs him _cost__i_ points of mana. However, for each bird summoned, Imp increases his mana capacity by _B_ points. Imp summons birds one by one, he can summon any number from 0 to _c__i_ birds from the _i_\-th nest.
Initially Imp stands under the first tree and has _W_ points of mana, and his mana capacity equals _W_ as well. He can only go forward, and each time he moves from a tree to the next one, he restores _X_ points of mana (but it can't exceed his current mana capacity). Moving only forward, what is the maximum number of birds Imp can summon?
## Input
The first line contains four integers _n_, _W_, _B_, _X_ (1 ≤ _n_ ≤ 103, 0 ≤ _W_, _B_, _X_ ≤ 109) — the number of trees, the initial points of mana, the number of points the mana capacity increases after a bird is summoned, and the number of points restored when Imp moves from a tree to the next one.
The second line contains _n_ integers _c_1, _c_2, ..., _c__n_ (0 ≤ _c__i_ ≤ 104) — where _c__i_ is the number of birds living in the _i_\-th nest. It is guaranteed that .
The third line contains _n_ integers _cost_1, _cost_2, ..., _cost__n_ (0 ≤ _cost__i_ ≤ 109), where _cost__i_ is the mana cost to summon a bird from the _i_\-th nest.
## Output
Print a single integer — the maximum number of birds Imp can summon.
[samples]
## Note
In the first sample base amount of Imp's mana is equal to 12 (with maximum capacity also equal to 12). After he summons two birds from the first nest, he loses 8 mana points, although his maximum capacity will not increase (since _B_ = 0). After this step his mana will be 4 of 12; during the move you will replenish 4 mana points, and hence own 8 mana out of 12 possible. Now it's optimal to take 4 birds from the second nest and spend 8 mana. The final answer will be — 6.
In the second sample the base amount of mana is equal to 1000. The right choice will be to simply pick all birds from the last nest. Note that Imp's mana doesn't restore while moving because it's initially full.
除了毛绒玩具，Imp 还是黄色小鸟的狂热粉丝！
为了召唤小鸟，Imp 需要强大的魔法。公园小径上有一排 #cf_span[n] 棵树，每棵树上都有一个鸟巢。第 #cf_span[i] 个鸟巢中有 #cf_span[ci] 只小鸟；要从这个鸟巢召唤一只小鸟，Imp 需要站在该树下，花费 #cf_span[costi] 点法力值。然而，每召唤一只小鸟，Imp 的法力上限就会增加 #cf_span[B] 点。Imp 一只一只地召唤小鸟，他可以从第 #cf_span[i] 个鸟巢中召唤 #cf_span[0] 到 #cf_span[ci] 只小鸟。
最初，Imp 站在第一棵树下，拥有 #cf_span[W] 点法力值，其法力上限也等于 #cf_span[W]。他只能向前移动，每次从一棵树移动到下一棵树时，他会恢复 #cf_span[X] 点法力值（但不能超过当前法力上限）。在只允许向前移动的前提下，Imp 最多能召唤多少只小鸟？
第一行包含四个整数 #cf_span[n], #cf_span[W], #cf_span[B], #cf_span[X]（#cf_span[1 ≤ n ≤ 103, 0 ≤ W, B, X ≤ 109]）— 树的数量、初始法力值、每召唤一只小鸟法力上限增加的点数、从一棵树移动到下一棵树时恢复的法力值。
第二行包含 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn]（#cf_span[0 ≤ ci ≤ 104]）— 其中 #cf_span[ci] 表示第 #cf_span[i] 个鸟巢中居住的小鸟数量。保证 。
第三行包含 #cf_span[n] 个整数 #cf_span[cost1, cost2, ..., costn]（#cf_span[0 ≤ costi ≤ 109]），其中 #cf_span[costi] 是从第 #cf_span[i] 个鸟巢召唤一只小鸟所需的法力值。
请输出一个整数 —— Imp 最多能召唤的小鸟数量。
在第一个样例中，Imp 的基础法力值为 #cf_span[12]（法力上限也为 #cf_span[12]）。在从第一个鸟巢召唤两只小鸟后，他损失了 #cf_span[8] 点法力，但法力上限不会增加（因为 #cf_span[B = 0]）。此时他的法力为 #cf_span[4]（上限为 #cf_span[12]）；移动时恢复 #cf_span[4] 点法力，因此他拥有 #cf_span[8] 点法力（上限仍为 #cf_span[12]）。此时最优策略是从第二个鸟巢召唤 #cf_span[4] 只小鸟，花费 #cf_span[8] 点法力。最终答案为 — #cf_span[6]。
在第二个样例中，基础法力值为 #cf_span[1000]。最优策略是直接从最后一个鸟巢召唤所有小鸟。注意，由于初始法力已满，移动时法力不会恢复。
## Input
第一行包含四个整数 #cf_span[n], #cf_span[W], #cf_span[B], #cf_span[X]（#cf_span[1 ≤ n ≤ 103, 0 ≤ W, B, X ≤ 109]）— 树的数量、初始法力值、每召唤一只小鸟法力上限增加的点数、从一棵树移动到下一棵树时恢复的法力值。第二行包含 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn]（#cf_span[0 ≤ ci ≤ 104]）— 其中 #cf_span[ci] 表示第 #cf_span[i] 个鸟巢中居住的小鸟数量。保证 。第三行包含 #cf_span[n] 个整数 #cf_span[cost1, cost2, ..., costn]（#cf_span[0 ≤ costi ≤ 109]），其中 #cf_span[costi] 是从第 #cf_span[i] 个鸟巢召唤一只小鸟所需的法力值。
## Output
请输出一个整数 —— Imp 最多能召唤的小鸟数量。
[samples]
## Note
在第一个样例中，Imp 的基础法力值为 #cf_span[12]（法力上限也为 #cf_span[12]）。在从第一个鸟巢召唤两只小鸟后，他损失了 #cf_span[8] 点法力，但法力上限不会增加（因为 #cf_span[B = 0]）。此时他的法力为 #cf_span[4]（上限为 #cf_span[12]）；移动时恢复 #cf_span[4] 点法力，因此他拥有 #cf_span[8] 点法力（上限仍为 #cf_span[12]）。此时最优策略是从第二个鸟巢召唤 #cf_span[4] 只小鸟，花费 #cf_span[8] 点法力。最终答案为 — #cf_span[6]。
在第二个样例中，基础法力值为 #cf_span[1000]。最优策略是直接从最后一个鸟巢召唤所有小鸟。注意，由于初始法力已满，移动时法力不会恢复。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of trees.
Let $ W, B, X \in \mathbb{Z}_{\geq 0} $ be the initial mana, mana capacity increase per bird, and mana restored per move, respectively.
Let $ C = (c_1, c_2, \dots, c_n) \in \mathbb{Z}_{\geq 0}^n $, where $ c_i $ is the number of birds in nest $ i $.
Let $ \text{Cost} = (\text{cost}_1, \text{cost}_2, \dots, \text{cost}_n) \in \mathbb{Z}_{\geq 0}^n $, where $ \text{cost}_i $ is the mana cost per bird at tree $ i $.
Let $ x_i \in \mathbb{Z} $ denote the number of birds summoned from nest $ i $, with $ 0 \leq x_i \leq c_i $.
Let $ M_i \in \mathbb{Z}_{\geq 0} $ be the mana available at tree $ i $ before summoning.
Let $ K_i \in \mathbb{Z}_{\geq 0} $ be the mana capacity after summoning birds at tree $ i $, with $ K_0 = W $.
**Constraints**
1. $ 1 \leq n \leq 10^3 $
2. $ 0 \leq W, B, X \leq 10^9 $
3. $ 0 \leq c_i \leq 10^4 $ for all $ i \in \{1, \dots, n\} $
4. $ 0 \leq \text{cost}_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $
5. Initial state: $ M_1 = W $, $ K_1 = W $
6. For $ i \in \{1, \dots, n-1\} $:
$$
M_{i+1} = \min(K_i - \sum_{j=1}^{i} x_j \cdot \text{cost}_j + X, \, K_i + B \cdot \sum_{j=1}^{i} x_j)
$$
$$
K_{i+1} = W + B \cdot \sum_{j=1}^{i} x_j
$$
7. At tree $ i $: $ \sum_{j=1}^{i} x_j \cdot \text{cost}_j \leq M_i $
**Objective**
Maximize total birds summoned:
$$
\max \sum_{i=1}^{n} x_i
$$
subject to the above constraints.
API Response (JSON)
{
"problem": {
"name": "E. Birds",
"description": {
"content": "Apart from plush toys, Imp is a huge fan of little yellow birds! <center></center>To summon birds, Imp needs stro",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF922E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Apart from plush toys, Imp is a huge fan of little yellow birds!\n\n<center></center>To summon birds, Imp needs stro...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "除了毛绒玩具，Imp 还是黄色小鸟的狂热粉丝！\n\n为了召唤小鸟，Imp 需要强大的魔法。公园小径上有一排 #cf_span[n] 棵树，每棵树上都有一个鸟巢。第 #cf_span[i] 个鸟巢中有 #cf_span[ci] 只小鸟；要从这个鸟巢召唤一只小鸟，Imp 需要站在该树下，花费 #cf_span[costi] 点法力值。然而，每召唤一只小鸟，Imp 的法力上限就会增加 #cf_span[B...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of trees. \nLet $ W, B, X \\in \\mathbb{Z}_{\\geq 0} $ be the initial mana, mana capacity increase per bird, and mana restored per move, respect...",
"is_translate": false,
"language": "Formal"
}
]
}