测试数据来自 system/1464

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　小H和他的小伙伴们最近准备组织一场登山活动！

　　由于山势险峻，登山者只能从一侧上山，从另一侧下山，任意时刻，最多有一人在登山，一人在下山，同时山顶有供登山者休息等待的平台。

　　参与活动共有 \(n\) 个小朋友，第 \(i\) 个小朋友登上山顶的时间为 \(u_i\) 分钟，下山的时间为 \(d_i\) 分钟。每个小朋友上山和下山都必需要有一个人引导，小H负责上山引导，大H负责下山引导，一群小朋友可能会在山顶等到大H的引导。小朋友们上山和下山的顺序可能不同。

　　现在请你计算整个登山活动（所有人上山并下山）的需要的最少时间。

【输入格式】

　　输入文件的第一行为一个整数 \(n\)，表示参与登山活动的小朋友数量。
　　接下来的 \(n\) 行，每行两个整数：\(u_i\) 和 \(d_i\)，分别表示第 \(i\) 个小朋友登山的时间和下山的时间（单位：分钟）。

【输出格式】

　　输出文件只有一行，包含一个非负整数，表示活动完成的最少时间（单位为分钟）。

【输入输出样例1】

　Input

3
6 4
8 1
2 3

　Output

17

【输入输出样例1说明】

　　上山顺序为3,1,2，下山顺序也是3,1,2。
　　此时第3个小朋友登山需要2分钟，下山需要3分钟，第1个小朋友在第8分钟末登山山顶，第12分钟末下山，第3个人在第16分钟末登上山顶后立即下山，在第17分钟末下山。

【输入输出样例2】

　Input

5
1 4
2 5
3 6
4 2
5 3

　Output

21

【输入输出样例2说明】

　　上山按照1 2 3 4 5的顺序，下山按 1 2 3 5 4的顺序，活动完成的时间时21分钟，图示方案如下：

　　当然按照1 2 3 4 5的顺序下山，最后活动完成的时间也是21。

【数据说明】

　　对于 \(30\%\) 的数据，\(1 ≤ n ≤ 10\)
　　对于 \(100\%\) 的数据，\(1 ≤ n ≤ 25000\)，\(1 ≤ u_i,d_i ≤ 1000\)

【来源】

　　Mr.he