← 返回题目列表

AtCoder · abc352_c

E. 站在肩膀上

中文机器翻译题面 查看原题

分数: 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