货币兑换

题目描述

有 $N$ 个编号从 $1$ 到 $N$ 的国家。每个国家 $i$ 初始持有 $A_i$ 单位货币。高桥可以执行以下操作任意次数（包括零次）：

1. 选择整数 $i$（$1 \leq i \leq N-1$）
2. 如果当前持有至少 $S_i$ 单位的 $i$ 国货币：
   • 支付 $S_i$ 单位的 $i$ 国货币
   • 获得 $T_i$ 单位的 $(i+1)$ 国货币

求最终能获得的第 $N$ 国货币的最大数量。

约束条件

• 所有输入为整数
• $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$

输入格式

从标准输入按以下格式读取数据：

$N$

$A_1$ $A_2$ $\ldots$ $A_N$

$S_1$ $T_1$

$S_2$ $T_2$

$\vdots$

$S_{N-1}$ $T_{N-1}$

输出格式

一个整数，表示最多可以兑换多少$N$国货币

4
5 7 0 3
2 2
4 3
5 2

5

样例1解释

初始状态

设序列 $A = (A_1, A_2, A_3, A_4)$ 表示高桥持有的各国货币数量，初始状态为：

操作流程

通过以下四次操作逐步优化货币持有量：

1. ​操作 $i=2$

   • 支付：4 单位国家2的货币
   • 获得：3 单位国家3的货币
   • 更新后状态：$$A = (5, \ 3, \ 3, \ 3)$$

2. ​操作 $i=1$

   • 支付：2 单位国家1的货币
   • 获得：2 单位国家2的货币
   • 更新后状态：$$A = (3, \ 5, \ 3, \ 3)$$

3. ​再次操作 $i=2$

   • 支付：4 单位国家2的货币
   • 获得：3 单位国家3的货币
   • 更新后状态：$$A = (3, \ 1, \ 6, \ 3)$$

4. ​操作 $i=3$

   • 支付：5 单位国家3的货币
   • 获得：2 单位国家4的货币
   • 更新后状态：$$A = (3, \ 1, \ 1, \ 5)$$

最终结果

此时高桥持有 ​5 单位国家4的货币，这是通过操作能获得的最大值。

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