分数: 150 点
问题陈述
有 N 国家/地区编号 1 to N。对于每个 i = 1, 2, \ldots, N,高桥有 A_i 国家/地区货币单位 i.
Takahashi 可以重复以下操作任意次数,可能为零:
- 首先,选择一个整数 i 之间 1 和 N-1,包括在内。
- 那么,如果高桥至少有 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}
输出
打印答案。
示例输入 1
4 5 7 0 3 2 2 4 3 5 2
示例输出 1
5
在下面的解释中,让序列 A = (A_1, A_2, A_3, A_4) 代表高桥拥有的国家的货币单位数量。最初, A = (5, 7, 0, 3).
考虑执行四次操作,如下所示:
- 选择 i = 2,支付四个单位的国家货币 2,并获得三个单位的国家货币 3。现在, A = (5, 3, 3, 3).
- 选择 i = 1,支付两个单位的国家货币 1,并获得两个单位的国家货币 2。现在, A = (3, 5, 3, 3).
- 选择 i = 2,支付四个单位的国家货币 2,并获得三个单位的国家货币 3。现在, A = (3, 1, 6, 3).
- 选择 i = 3,支付五单位国家货币 3,并获得两个单位的国家货币 4。现在, A = (3, 1, 1, 5).
此时,高桥拥有五个单位的国家货币 4,这是可能的最大数量。
示例输入 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
示例输出 2
45