AT_abc341_b [ABC341B] Foreign Exchange

有 $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}$

请输出答案。

## 限制条件 - 所有输入的值均为整数。 - $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 翻译