

Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 150 点
問題文
1 から N までの番号がつけられた N 個の国があり、i = 1, 2, \ldots, N について、高橋君は国 i の通貨を A_i 単位持っています。
高橋君は、下記の操作を好きな回数( 0 回でも良い)繰り返します。
- まず、1 以上 N-1 以下の整数 i を選ぶ。
- その後、国 i の通貨を S_i 単位以上持っているなら、下記の行動を 1 回行う。
- 国 i の通貨を S_i 単位だけ支払い、国 (i+1) の通貨を T_i 単位だけ獲得する。
最終的に高橋君が持っている国 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) です。
下記の通りに 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 であり、これが考えられる最大値です。
入力例 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
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