Time Limit: 2 sec / Memory Limit: 1024 MB

问题陈述

有 $N$ 个巨人，他们的名字分别是 $1$ 到 $N$ 。当巨人 $i$ 站在地上时，他们的肩高是 A_i，头高是 B_i ​

你可以选择 $(1, 2, \ldots, N)$ 的 (P₁, P₂, ..., 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}$ 的头部距离地面的最大可能高度。

限制因素

• $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$

Output

Print the answer.

Sample Input 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$ 。

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