外汇兑换

题目描述

有 $N$ 个国家，编号为 $1$ 到 $N$。对每个 $i = 1, 2, \ldots, N$，高桥君拥有 $A_i$ 单位的第 $i$ 国货币。

高桥君可以任意多次（可以为 0 次）重复以下操作：

首先，选择一个 $1$ 到 $N-1$（含端点）之间的整数 $i$。

然后，如果高桥君至少拥有 $S_i$ 单位的第 $i$ 国货币，则执行一次以下动作：

支付 $S_i$ 单位的第 $i$ 国货币，获得 $T_i$ 单位的第 $(i+1)$ 国货币。

输出最后高桥君最多能拥有多少单位第 $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

在下面的说明中，用序列 $A = (A_1, A_2, A_3, A_4)$ 表示高桥君拥有的各国货币数量。初始时，$A = (5, 7, 0, 3)$。

考虑按如下方式进行 4 次操作：

• 选择 $i = 2$，支付 4 单位第 2 国货币，获得 3 单位第 3 国货币。此时，$A = (5, 3, 3, 3)$。
• 选择 $i = 1$，支付 2 单位第 1 国货币，获得 2 单位第 2 国货币。此时，$A = (3, 5, 3, 3)$。
• 选择 $i = 2$，支付 4 单位第 2 国货币，获得 3 单位第 3 国货币。此时，$A = (3, 1, 6, 3)$。
• 选择 $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

数据范围

• 所有输入值均为整数
• $2 \le N \le 2 \times 10^5$
• $0 \le A_i \le 10^9$
• $1 \le T_i \le S_i \le 10^9$