103411: [Atcoder]ABC341 B - Foreign Exchange

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：7 Solved：0

Description

Score: $150$ points

Problem Statement

There are $N$ countries numbered $1$ to $N$. For each $i = 1, 2, \ldots, N$, Takahashi has $A_i$ units of the currency of country $i$.

Takahashi can repeat the following operation any number of times, possibly zero:

  • First, choose an integer $i$ between $1$ and $N-1$, inclusive.
  • Then, if Takahashi has at least $S_i$ units of the currency of country $i$, he performs the following action once:
    • Pay $S_i$ units of the currency of country $i$ and gain $T_i$ units of the currency of country $(i+1)$.

Print the maximum possible number of units of the currency of country $N$ that Takahashi could have in the end.

Constraints

  • All input values are integers.
  • $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$

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

4
5 7 0 3
2 2
4 3
5 2

Sample Output 1

5

In the following explanation, let the sequence $A = (A_1, A_2, A_3, A_4)$ represent the numbers of units of the currencies of the countries Takahashi has. Initially, $A = (5, 7, 0, 3)$.

Consider performing the operation four times as follows:

  • Choose $i = 2$, pay four units of the currency of country $2$, and gain three units of the currency of country $3$. Now, $A = (5, 3, 3, 3)$.
  • Choose $i = 1$, pay two units of the currency of country $1$, and gain two units of the currency of country $2$. Now, $A = (3, 5, 3, 3)$.
  • Choose $i = 2$, pay four units of the currency of country $2$, and gain three units of the currency of country $3$. Now, $A = (3, 1, 6, 3)$.
  • Choose $i = 3$, pay five units of the currency of country $3$, and gain two units of the currency of country $4$. Now, $A = (3, 1, 1, 5)$.

At this point, Takahashi has five units of the currency of country $4$, which is the maximum possible number.

Sample Input 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

Sample Output 2

45

Input

Output

得分：150分 部分 问题描述 有编号为1到N的N个国家。对于每个$i = 1, 2, \ldots, N$，Takahashi拥有国家i的货币单位$A_i$。 Takahashi可以重复执行以下操作任意次数，包括0次： 1. 首先，选择一个在1到N-1之间的整数$i$，包括1和N-1。 2. 然后，如果Takahashi拥有至少$S_i$单位的国家i的货币，他执行以下操作一次： - 付出$S_i$单位的国家i的货币，并获得国家$(i+1)$的$T_i$单位的货币。 打印Takahashi在最后可能拥有的国家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)$表示Takahashi拥有的国家货币单位的数量。最初，$A = (5, 7, 0, 3)$。 考虑按以下方式执行操作四次： 1. 选择$i = 2$，付出四个国家2的货币单位，并获得三个国家3的货币单位。现在，$A = (5, 3, 3, 3)$。 2. 选择$i = 1$，付出两个国家1的货币单位，并获得两个国家2的货币单位。现在，$A = (3, 5, 3, 3)$。 3. 选择$i = 2$，付出四个国家2的货币单位，并获得三个国家3的货币单位。现在，$A = (3, 1, 6, 3)$。 4. 选择$i = 3$，付出五个国家3的货币单位，并获得两个国家4的货币单位。现在，$A = (3, 1, 1, 5)$。 此时，Takahashi拥有五个国家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 ```

Source/Category

加入题单

算法标签：