[ABC352] C - Standing On The Shoulders

C - Standing On The Shoulders

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 300 分

题面

有 个巨人，编号为 到 。当第 个巨人站在地面上时，他们的肩膀高度为 ，头部高度为 。

你可以选择一个 的排列 ，按照以下规则来堆叠这 个巨人：

• 首先，把巨人 放在地面上。巨人 的肩膀高度将是 ，他们的头部高度将是 。

• 对于 ，依次将巨人 放在巨人 的肩膀上。如果巨人 的肩膀高度为 ，那么巨人 的肩膀高度将是 ，他们的头部高度将是 。

找到最高的巨人 的头部高度可能的最大值。

限制条件

• 所有输入值均为整数。

---

输入

输入来自标准输入，格式如下：

输出

输出答案。

---

输入样例 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