← 返回题目列表

AtCoder · abc341_b

D. 外汇

中文机器翻译题面 查看原题

分数: 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