Farmer John 发现，当附近有另一头奶牛作为精神支持时，他的奶牛更容易挤奶。因此，他想将他的 M 头奶牛（M≤1,000,000,000，M 偶数）分成 M/2 对。然后每对奶牛将被带到谷仓中的一个单独的隔间进行挤奶。每个 M/2 隔间的挤奶工作将同时进行。

更复杂的是，Farmer John 的每头奶牛都有不同的产奶量。如果牛奶输出 A 和 B 的奶牛成对出现，那么总共需要 A+B 个单位的时间来挤奶。

请帮助 Farmer John 确定完成整个挤奶过程所需的最短时间，假设他以最佳方式将奶牛配对。

输入格式（文件pairup.in）：

输入的第一行包含 N (1≤N≤100,000)。接下来的 N 行中的每一行都包含两个整数 x 和 y，表示 FJ 有 x 头奶牛，每头奶牛的产奶量为 y (1≤y≤1,000,000,000)。x 的总和是 M，即奶牛的总数。

输出格式（文件pairup.out）：

打印出 FJ 的奶牛挤奶所需的最短时间，假设它们是最佳配对。

SAMPLE INPUT:

3
1 8
2 5
1 2

SAMPLE OUTPUT:

10

在这里，如果输出 8+2 的奶牛配对，输出 5+5 的奶牛配对，则两个摊位都需要 10 个单位的挤奶时间。由于挤奶是同时进行的，因此整个过程将在 10 个单位时间后完成。任何其他配对都是次优的，导致挤奶的时间超过 10 个单位。