测试数据来自 system/3140

作业已超过截止时间，您无法递交本题目。

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

---

【问题描述】

　　老师发现，两个学生一起完成作业的效率会更高，于是他把他的 \(N\) 名学生（\(N \leq 1,000,000,000\)，\(N\) 为偶数）分成 \(N/2\) 对。每对学生将被安排在单独的隔间完成作业。所有隔间学生完成作业是同时进行的。

　　为了便于分配，老师给出一个作业效率量化的数字。如果作业效率为 \(A\) 和 \(B\) 的两名学生被配对，那么它们完成作业总共需要 \(A+B\) 单位时间。

　　请帮助 H老师 确定整个所有学生完成作业的最少时间，假设他以最佳方式配对学生。

【输入格式】

　　输入的第一行包含 \(T\)（\(1 \leq T \leq 100,000\)）。
　　接下来的 \(T\) 行每行包含两个整数 \(x\) 和 \(y\)，表示有 \(x\) 个作业效率为 \(y\) 的学生（\(1 \leq y \leq 1,000,000,000\)）。所有 \(x\) 的总和为 \(N\)，即学生的总数。

【输出格式】

　输出完成作业所需的最少时间，假设它们以最佳方式配对。

【输入输出样例1】

　Input

3
1 8
2 5
1 2

　Output

10

【样例1解释】

　　在这里，如果作业效率为 8 和 2 的学生配对，作业效率为 5 和 5 的学生配对，那么两个隔间的作业时间均为 10 单位时间。由于作业是同时进行的，因此整个作业过程将在 10 单位时间后完成。任何其他配对方式都会导致某个隔间的作业时间超过 10 单位时间，因此不是最优的。

【数据说明】

　　

【来源】

　　Nr.he