HUSTOJ

Description

农场主约翰发现，如果附近有另一头母牛作为精神支柱，他的母牛更容易挤奶。因此，他想把他的M头母牛（ M≤100000000，M偶数）分成M/2对。然后，每对母牛将被领到谷仓的一个单独的摊位上挤奶。这些M/2档的挤奶将同时进行。
让事情复杂一点的是，每头奶牛都有不同的产奶量。如果产奶量为A 和 B的奶牛配对，那么总共需要A+B单位的时间来产奶。
请帮助农场主约翰确定完成整个挤奶过程所需的最短时间，假设他以最好的方式将奶牛配对。

Input

第一行为一个正整数N。(1≤N≤100000)

接下来有N行，每行两个正整数x和y，表示有x头奶牛的产奶量为y。保证所有x的总和等于M

Output

同时产奶，问所需的最短时间是多少

Sample Input Copy

Sample Output Copy

HINT

奶牛的产奶量分别为8,5,5,2。

让8和2配对，5和5配对，则产奶时间分别为10,10，所以这两对奶牛同时产奶的时间为10.

Source/Category

USACO 贪心