/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
N 人の巨人がいます。巨人にはそれぞれ 1, 2, \ldots, N の名前がついており、巨人 i が地面に立ったとき、肩の高さは A_i、頭の高さは B_i となります。
あなたは (1, 2, \ldots, N) を並べ替えて得られる数列 (P_1, P_2, \ldots, P_N) を選び、以下の規則に従って N 人の巨人を積み上げることができます。
-
まず地面に巨人 P_1 を立たせる。巨人 P_1 の肩は地面を基準として A_{P_1}、頭は地面を基準として B_{P_1} の高さとなる。
-
i = 1, 2, \ldots, N - 1 の順に巨人 P_i の肩の上に巨人 P_{i + 1} を立たせる。巨人 P_i の肩が地面を基準として高さ t のとき、巨人 P_{i + 1} の肩は地面を基準として t + A_{P_{i + 1}}、頭は地面を基準として t + B_{P_{i + 1}} の高さとなる。
一番上に立っている巨人、すなわち巨人 P_N の地面を基準とした頭の高さとして実現できる最大値を求めてください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq B_i \leq 10^9
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
答えを出力せよ。
入力例 1
3 4 10 5 8 2 9
出力例 1
18
(P_1, P_2, P_3) = (2, 1, 3) とすると、地面を基準として巨人 2 は肩の高さが 5、頭の高さが 8、巨人 1 は肩の高さが 9、頭の高さが 15、巨人 3 は肩の高さが 11、頭の高さが 18 となります。
一番上に立っている巨人の頭の高さが地面を基準として 18 より大きくなることはないため 18 を出力します。
入力例 2
5 1 1 1 1 1 1 1 1 1 1
出力例 2
5
入力例 3
10 690830957 868532399 741145463 930111470 612846445 948344128 540375785 925723427 723092548 925021315 928915367 973970164 563314352 832796216 562681294 868338948 923012648 954764623 691107436 891127278
出力例 3
7362669937
Score: 300 points
Problem Statement
There are N giants, named 1 to N. When giant i stands on the ground, their shoulder height is A_i, and their head height is B_i.
You can choose a permutation (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N) and stack the N giants according to the following rules:
-
First, place giant P_1 on the ground. The giant P_1's shoulder will be at a height of A_{P_1} from the ground, and their head will be at a height of B_{P_1} from the ground.
-
For i = 1, 2, \ldots, N - 1 in order, place giant P_{i + 1} on the shoulders of giant P_i. If giant P_i's shoulders are at a height of t from the ground, then giant P_{i + 1}'s shoulders will be at a height of t + A_{P_{i + 1}} from the ground, and their head will be at a height of t + B_{P_{i + 1}} from the ground.
Find the maximum possible height of the head of the topmost giant P_N from the ground.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq B_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
Print the answer.
Sample Input 1
3 4 10 5 8 2 9
Sample Output 1
18
If (P_1, P_2, P_3) = (2, 1, 3), then measuring from the ground, giant 2 has a shoulder height of 5 and a head height of 8, giant 1 has a shoulder height of 9 and a head height of 15, and giant 3 has a shoulder height of 11 and a head height of 18.
The head height of the topmost giant from the ground cannot be greater than 18, so print 18.
Sample Input 2
5 1 1 1 1 1 1 1 1 1 1
Sample Output 2
5
Sample Input 3
10 690830957 868532399 741145463 930111470 612846445 948344128 540375785 925723427 723092548 925021315 928915367 973970164 563314352 832796216 562681294 868338948 923012648 954764623 691107436 891127278
Sample Output 3
7362669937