分数: 300 点
问题陈述
有 N 巨人,命名 1 to N。当巨人 i 站在地面上,他们的肩高是 A_i,他们的头高是 B_i.
您可以选择排列 (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, 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
输出
打印答案。
示例输入 1
3 4 10 5 8 2 9
示例输出 1
18
If (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