题目描述

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

高桥君可以喜欢地重复以下操作任意次数（可以为 $0$ 次）：

• 首先，选择一个整数 $i$，满足 $1 \leq i \leq N-1$。
• 然后，如果高桥君持有第 $i$ 个国家的货币不少于 $S_i$ 单位，则可以执行以下操作一次：
  • 支付第 $i$ 个国家的货币 $S_i$ 单位，并获得第 $i+1$ 个国家的货币 $T_i$ 单位。

请输出高桥君最终可能持有的第 $N$ 个国家货币的最大单位数。

输入格式

输入以如下格式从标准输入读入。

$N$
$A_1\ A_2\ \ldots\ A_N$
$S_1\ T_1$
$S_2\ T_2$
$\vdots$
$S_{N-1}\ T_{N-1}$

输出格式

请输出答案。

样例 1

输入

4
5 7 0 3
2 2
4 3
5 2

输出

5

样例 2

输入

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$

样例解释 1

在以下说明中，用数列 $A=(A_1, A_2, A_3, A_4)$ 表示高桥君持有的各国货币单位数。初始时，$A=(5, 7, 0, 3)$。考虑如下顺序进行 $4$ 次操作：

• 选择 $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)$。

此时，高桥君最终持有的第 $4$ 国货币单位数为 $5$，这是可能的最大值。

由 ChatGPT 4.1 翻译