4157： Standing On The Shoulders

# Standing On The Shoulders ### 内存 1024MB ### 时间 2S ## 题目描述 有$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$ ## 输出格式 输出所求答案。 ## 输入输出样例 ### 输入样例1 ``` 3 4 10 5 8 2 9 ``` ### 输出样例1 ``` 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 ``` ## 数据范围与提示 【样例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$，所有输入值都是整数。 ## 题目来源 ABC352C