A - Closing Time of the Reception Window Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

ある役所には受付窓口が 1 つだけあり、N 人の来客に番号 1, 2, \ldots, N の順番で対応します。窓口では同時に 1 人の来客にしか対応できません。

i 番目の来客は時刻 A_i に役所に到着し、対応には B_i の時間がかかります。来客の到着時刻は番号順に単調非減少、すなわち A_1 \leq A_2 \leq \cdots \leq A_N が保証されます。

窓口は時刻 0 以降に対応可能であり、来客 1 から来客 N まで必ずこの番号順に対応します。来客 i への対応は、窓口が空いていて、かつ来客 i が到着済みである最も早い時刻に開始されます。来客 i の対応開始時刻を S_i とすると、

  • S_1 = A_1
  • S_i = \max(S_{i-1} + B_{i-1},\ A_i) （i \geq 2）

であり、来客 i への対応は時刻 S_i + B_i に終了します。

最後の来客（来客 N）への対応が終了する時刻 S_N + B_N を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq A_1 \leq A_2 \leq \cdots \leq A_N \leq 10^9
  • 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
  • 入力はすべて整数

入力

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N
  • 1 行目には、来客の人数を表す整数 N が与えられる。
  • 続く N 行のうち i 行目には、i 番目の来客の到着時刻 A_i と対応にかかる時間 B_i がスペース区切りで与えられる。

出力

最後の来客への対応が終了する時刻を 1 行で出力せよ。

入力例 1

3
0 3
1 2
5 4

出力例 1

9

入力例 2

4
2 1
10 2
10 3
20 1

出力例 2

21

入力例 3

8
0 5
1 3
4 2
10 7
10 1
15 4
30 6
31 2

出力例 3

38

入力例 4

15
0 2
0 3
1 5
2 1
2 4
3 2
5 6
8 1
8 3
10 2
13 5
13 1
20 4
21 2
21 7

出力例 4

48

入力例 5

1
1000000000 1000000000

出力例 5

2000000000

Score : 266 pts

Problem Statement

A certain government office has only 1 service window, which serves N visitors in order, numbered 1, 2, \ldots, N. The window can serve only 1 visitor at a time.

The i-th visitor arrives at the office at time A_i, and serving them takes B_i units of time. It is guaranteed that the arrival times are non-decreasing in order of their numbers, i.e., A_1 \leq A_2 \leq \cdots \leq A_N.

The window is available for service from time 0 onwards, and it always serves visitors in order from visitor 1 to visitor N. Service for visitor i begins at the earliest time when the window is free and visitor i has already arrived. Letting S_i denote the start time of service for visitor i:

  • S_1 = A_1
  • S_i = \max(S_{i-1} + B_{i-1},\ A_i) （i \geq 2）

Service for visitor i ends at time S_i + B_i.

Find the time S_N + B_N at which service for the last visitor (visitor N) ends.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq A_1 \leq A_2 \leq \cdots \leq A_N \leq 10^9
  • 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
  • All inputs are integers.

Input

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N
  • The first line contains an integer N representing the number of visitors.
  • The following N lines each contain, on the i-th line, the arrival time A_i and the service duration B_i of the i-th visitor, separated by a space.

Output

Print the time at which service for the last visitor ends, on a single line.

Sample Input 1

3
0 3
1 2
5 4

Sample Output 1

9

Sample Input 2

4
2 1
10 2
10 3
20 1

Sample Output 2

21

Sample Input 3

8
0 5
1 3
4 2
10 7
10 1
15 4
30 6
31 2

Sample Output 3

38

Sample Input 4

15
0 2
0 3
1 5
2 1
2 4
3 2
5 6
8 1
8 3
10 2
13 5
13 1
20 4
21 2
21 7

Sample Output 4

48

Sample Input 5

1
1000000000 1000000000

Sample Output 5

2000000000