Standing On The Shoulders

题目描述

有 $N$ 个巨人，编号为 $1$ 到 $N$。当巨人 $i$ 站在地面上时，他们的肩膀高度为 $A_i$，头顶高度为 $B_i$。 你可以选择一个 $(1,2,\ldots,N)$ 的排列 $(P_1, P_2, \ldots, 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$ 的头顶离地面的最大可能高度。

输入格式

输入由标准输入按以下格式提供： $N$ $A_1$ $B_1$ $A_2$ $B_2$ \vdots $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
563314352 832796216
562681294 868338948
923012648 954764623
691107436 891127278

7362669937

提示

$2 \leq N \leq 2 \times 10^5$ $1 \leq A_i \leq B_i \leq 10^9$ 所有输入值均为整数。如果 $(P_1, P_2, P_3) = (2, 1, 3)$，那么从地面测量，巨人 $2$ 的肩膀高度为 $5$，头顶高度为 $8$，巨人 $1$ 的肩膀高度为 $9$，头顶高度为 $15$，巨人 $3$ 的肩膀高度为 $11$，头顶高度为 $18$。 最上面巨人的头顶离地面的高度不可能大于 $18$，所以输出 $18$。

标签: AtCoder|abc352C

来源

AtCoder|abc352C