站在巨人的肩膀上

题目描述

有 $N$ 个巨人,编号为 $1$ 到 $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 + 1}$ 放到巨人 $P_i$ 的肩膀上。如果巨人 $P_i$ 的肩膀离地面高度为 $t$,则巨人 $P_{i + 1}$ 的肩膀离地面高度为 $t + A_{P_{i + 1}}$,头顶离地面高度为 $t + B_{P_{i + 1}}$。

求最顶层巨人 $P_N$ 的头顶离地面高度的最大可能值。

输入格式

输入按以下格式从标准输入给出:

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

输出格式

输出答案。

样例

3
4 10
5 8
2 9

18

若 $(P_1, P_2, P_3) = (2, 1, 3)$,则从地面起,巨人 $2$ 的肩膀高度为 $5$,头顶高度为 $8$;巨人 $1$ 的肩膀高度为 $9$,头顶高度为 $15$;巨人 $3$ 的肩膀高度为 $11$,头顶高度为 $18$。

最顶层巨人的头顶离地面高度不可能大于 $18$,因此输出 $18$。

5
1 1
1 1
1 1
1 1
1 1

5

10
690830957 868532399
741145463 930111470
612846445 948344128
540375785 925723427
723092548 925021315
928915367 973970164
563314352 832796216
562681294 868338948
923012648 954764623
691107436 891127278

7362669937

数据范围

• $2 \le N \le 2 \times 10^5$
• $1 \le A_i \le B_i \le 10^9$
• 输入中的所有值均为整数