AT_abc352_c [ABC352C] Standing On The Shoulders

题目描述

有 $N$ 个巨人。每个巨人分别被命名为 $1, 2, \ldots, N$。当巨人 $i$ 站在地面上时，他的肩膀高度为 $A_i$，头顶高度为 $B_i$。

你可以选择一个 $1$ 到 $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}}$（均以地面为基准）。

请你求出，所有可能的排列中，最上面那个巨人的头顶高度（以地面为基准）所能达到的最大值。

输入格式

输入按以下格式从标准输入读入。

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3
4 10
5 8
2 9

输出 #1

18

输入输出样例 #2

输入 #2

5
1 1
1 1
1 1
1 1
1 1

输出 #2

5

输入输出样例 #3

输入 #3

10
690830957 868532399
741145463 930111470
612846445 948344128
540375785 925723427
723092548 925021315
928915367 973970164
563314352 832796216
562681294 868338948
923012648 954764623
691107436 891127278

输出 #3

7362669937

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq B_i \leq 10^9$
• 输入的所有值均为整数

样例解释 1

如果选择排列 $(P_1, P_2, P_3) = (2, 1, 3)$，那么以地面为基准，巨人 $2$ 的肩膀高度为 $5$，头顶高度为 $8$；巨人 $1$ 的肩膀高度为 $9$，头顶高度为 $15$；巨人 $3$ 的肩膀高度为 $11$，头顶高度为 $18$。最上面巨人的头顶高度以地面为基准为 $18$，无法再更高，因此输出 $18$。

由 ChatGPT 4.1 翻译