题目描述

有$N$个巨人，编号从$1$到$N$。当巨人$i$站在地上时，他们的肩膀高度为$A_i$，头部高度为$B_i$。

你可以选择一个$(1, 2, ..., N)$的排列$(P_1, P_2, ..., P_N)$，并按照以下规则堆叠这$N$个巨人：

1. 首先，将巨人$P_1$放在地上。巨人$P_1$的肩膀将位于距地面$A_{P_1}$的高度，头部将位于距地面$B_{P_1}$的高度。

2. 对于$i = 1, 2, ..., 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$

$\cdots$

$A_N$ $B_N$

输出格式

输出所求答案。

样例

3
4 10
5 8
2 9

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

7362669937

样例1解释

如果$(P_1, P_2, P_3)$ = $(2, 1, 3)$，那么从地面开始测量，巨人2的肩膀高度为5，头部高度为8，巨人1的肩膀高度为9，头部高度为15，巨人3的肩膀高度为11，头部高度为18。

最顶层巨人的头部距地面的高度不可能超过18，所以输出18。

数据范围

$2 ≤ N ≤ 2 × 10^5, 1 ≤ A_i ≤ B_i ≤ 10^9$，所有输入值都是整数。

来源

• AtCoder ABC352C