Foreign Exchange

题目描述

有 $N$ 个国家，编号为 $1$ 到 $N$。对于每个 $i = 1, 2, \ldots, N$，Takahashi 拥有国家 $i$ 的货币 $A_i$ 单位。 Takahashi 可以任意次数（可以为零次）重复下述操作：

首先，选择一个整数 $i$，满足 $1 \leq i \leq N-1$。 然后，如果 Takahashi 拥有至少 $S_i$ 单位的国家 $i$ 的货币，则执行以下动作一次： 支付 $S_i$ 单位的国家 $i$ 的货币，并获得 $T_i$ 单位的国家 $(i+1)$ 的货币。

输出 Takahashi 最终可能拥有的国家 $N$ 的货币的最大单位数。

输入格式

输入按下列格式从标准输入给出： $N$ $A_1$ $A_2$ $\ldots$ $A_N$ $S_1$ $T_1$ $S_2$ $T_2$ $\vdots$ $S_{N-1}$ $T_{N-1}$

输出格式

输出答案。

4
5 7 0 3
2 2
4 3
5 2

5

10
32 6 46 9 37 8 33 14 31 5
5 5
3 1
4 3
2 2
3 2
3 2
4 4
3 3
3 1

45

提示

所有输入值均为整数。 $2 \leq N \leq 2 \times 10^5$ $0 \leq A_i \leq 10^9$ $1 \leq T_i \leq S_i \leq 10^9$在下面的说明中，记序列 $A = (A_1, A_2, A_3, A_4)$ 表示 Takahashi 拥有的各国货币的数量。最初，$A = (5, 7, 0, 3)$。 考虑按如下顺序执行四次操作：

选择 $i = 2$，支付国家 $2$ 的货币 4 单位，获得国家 $3$ 的货币 3 单位。现在，$A = (5, 3, 3, 3)$。 选择 $i = 1$，支付国家 $1$ 的货币 2 单位，获得国家 $2$ 的货币 2 单位。现在，$A = (3, 5, 3, 3)$。 选择 $i = 2$，支付国家 $2$ 的货币 4 单位，获得国家 $3$ 的货币 3 单位。现在，$A = (3, 1, 6, 3)$。 选择 $i = 3$，支付国家 $3$ 的货币 5 单位，获得国家 $4$ 的货币 2 单位。现在，$A = (3, 1, 1, 5)$。

此时，Takahashi 拥有国家 $4$ 的货币 5 单位，这是可能的最大值。

标签: AtCoder|abc341B

来源

AtCoder|abc341B