B - バスツアー 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 266 点

問題文

高橋君は観光バスツアーの運営をしています。このツアーでは、バスが複数の停留所を順番に巡りながら乗客を乗せていきます。

ツアーには N 個の停留所があり、出発地点から順に停留所 1, 停留所 2, ..., 停留所 N と番号が付けられています。停留所 1 が最初の停留所で、停留所 N が最終目的地です。

バスは最初（停留所 1 で乗車が行われる前）には誰も乗っていません。

各停留所 i（1 \leq i \leq N）では、新たに A_i 人の乗客が乗車します。

さらに、各停留所 i（1 \leq i \leq N - 1）では、乗車の後、次の停留所 i + 1 への移動中に B_i 人の乗客が下車してツアーを離れます。ただし、そのときバスに乗っている人数が B_i 人未満の場合は、乗っている全員が下車します。

まとめると、各停留所 i で行われる処理は以下の通りです：

  1. A_i 人の乗客が新たに乗車する。
  2. i \leq N - 1 の場合、次の停留所への移動中に \min(\text{現在の乗客数}, B_i) 人が下車する。i = N の場合、下車は発生しない。

停留所 N での乗車が完了した時点で、バスに乗っている乗客の人数を求めてください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9（1 \leq i \leq N）
  • 0 \leq B_i \leq 10^9（1 \leq i \leq N - 1）
  • 入力はすべて整数

入力

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
A_N
  • 1 行目には、停留所の数を表す整数 N が与えられる。
  • i + 1 行目（1 \leq i \leq N - 1）には、停留所 i での乗車人数 A_i と下車人数 B_i がスペース区切りで与えられる。
  • N + 1 行目には、停留所 N での乗車人数 A_N のみが与えられる。

出力

停留所 N での乗車が完了した時点でバスに乗っている乗客の人数を 1 行で出力せよ。

入力例 1

3
5 2
3 1
4

出力例 1

9

入力例 2

3
2 10
1 5
3

出力例 2

3

入力例 3

6
10 3
5 4
8 20
7 2
3 1
6

出力例 3

13

入力例 4

10
1000000000 500000000
1000000000 200000000
500000000 1000000000
300000000 100000000
0 999999999
1000000000 1000000000
999999999 0
0 500000000
500000000 1000000000
123456789

出力例 4

123456789

入力例 5

2
0 0
0

出力例 5

0

Score : 266 pts

Problem Statement

Takahashi is operating a sightseeing bus tour. In this tour, a bus picks up passengers while visiting multiple stops in order.

The tour has N stops, numbered stop 1, stop 2, ..., stop N in order from the departure point. Stop 1 is the first stop, and stop N is the final destination.

The bus is initially empty (before any boarding takes place at stop 1).

At each stop i (1 \leq i \leq N), A_i new passengers board the bus.

Furthermore, at each stop i (1 \leq i \leq N - 1), after boarding, B_i passengers get off the bus and leave the tour during the trip to the next stop i + 1. However, if the number of passengers currently on the bus is less than B_i, all passengers on the bus get off.

In summary, the process at each stop i is as follows:

  1. A_i new passengers board the bus.
  2. If i \leq N - 1, during the trip to the next stop, \min(\text{current number of passengers}, B_i) passengers get off. If i = N, no passengers get off.

Find the number of passengers on the bus when boarding at stop N is completed.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 0 \leq B_i \leq 10^9 (1 \leq i \leq N - 1)
  • All input values are integers.

Input

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
A_N
  • The first line contains an integer N, representing the number of stops.
  • The (i + 1)-th line (1 \leq i \leq N - 1) contains the number of passengers boarding at stop i, A_i, and the number of passengers getting off, B_i, separated by a space.
  • The (N + 1)-th line contains only A_N, the number of passengers boarding at stop N.

Output

Print on a single line the number of passengers on the bus when boarding at stop N is completed.

Sample Input 1

3
5 2
3 1
4

Sample Output 1

9

Sample Input 2

3
2 10
1 5
3

Sample Output 2

3

Sample Input 3

6
10 3
5 4
8 20
7 2
3 1
6

Sample Output 3

13

Sample Input 4

10
1000000000 500000000
1000000000 200000000
500000000 1000000000
300000000 100000000
0 999999999
1000000000 1000000000
999999999 0
0 500000000
500000000 1000000000
123456789

Sample Output 4

123456789

Sample Input 5

2
0 0
0

Sample Output 5

0