【题目描述】

农民约翰发现，当附近有另一头奶牛提供精神支持时，他的奶牛都更容易挤奶。因此，他想把他的M头奶牛(M≤1,000,000,000，M为偶数)分成M/2对。然后，每一对奶牛将被引导到谷仓中单独的牛栏中挤奶。这些M/2隔间的挤奶将同时进行。

让事情变得有点复杂的是，农夫约翰的每头奶牛都有不同的产奶量。如果产奶量A和B的奶牛配成对，那么总共需要A+B个单位的时间来为它们挤奶。

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

【输入格式】(pairp.in):

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

【输出格式】(pairup.out):

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

【样例输入】:

3

1 8

2 5

1 2

【样例输出】:

10

【样例说明】

在这里，如果产量为8+2的奶牛被配对，产量为5+5的奶牛被配对，那么两个栏都需要10个单位的时间来挤奶。由于挤奶是同时进行的，因此整个过程将在10个单位时间后完成。任何其他配对都不是最优的，会导致奶棚需要超过10个单位的时间来挤奶。