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

题目描述：

某工厂有一条特殊的流水线，需要将 M 台设备两两配对组成工作站（总共组成 M/2 个工作站）。所有工作站会同时启动作业，整个流水线的完成时间由「耗时最长的工作站」决定。 每台设备都有一个「作业耗时基数」： • 如果两台基数为 A 和 B 的设备配对成一个工作站，这个工作站完成作业需要 A+B 个单位时间； • 工厂希望通过最优的配对方式，让整个流水线的完成时间尽可能短。 需要注意的是，工厂的设备是按「同基数批量统计」的：比如会统计 “有 x 台基数为 y 的设备”，而非单独列出每台设备的基数。 请你帮工厂计算，完成所有作业的最短时间是多少。

输入格式：

第一行输入整数 N，表示「不同基数的设备类型数」。 接下来 N 行，每行输入两个整数 x、y，表示有 x 台「作业耗时基数」为 y 的设备。 （注：所有 x 的总和为 M，M 是偶数，即设备总数能刚好两两配对）

输出格式：

输出一个整数，表示通过最优配对后，整个流水线完成作业的最短时间。

样例：

3
1 8
2 5
1 2

10

数据范围

1≤N≤10^5,2≤M≤10^9, M 是偶数,1≤y≤10^9

提示

设备明细：1 台基数 8 的设备、2 台基数 5 的设备、1 台基数 2 的设备（总计 4 台，可组成 2 个工作站）。 最佳配对方式： • 基数 8 和基数 2 的设备配对 → 耗时 8+2=10； • 两台基数 5 的设备配对 → 耗时 5+5=10； 所有工作站同时作业，最长耗时为 10，因此总完成时间为 10。