Paired Up

Farmer John finds that his cows are each easier to milk when they have another cow nearby for moral support. He therefore wants to take his $M$ cows ($M \le 1\,000\,000\,000$, $M$ even) and partition them into $M/2$ pairs. Each pair of cows is then ushered off to a separate stall in the barn for milking. The milking in all $M/2$ stalls takes place simultaneously.

Each cow has its own milk output. If cows with milk outputs $A$ and $B$ are paired up, it takes a total of $A+B$ units of time to milk them both.

Determine the minimum possible amount of time the entire milking process takes to complete, assuming Farmer John pairs the cows up in the best possible way.

The first line contains $N$ ($1 \le N \le 100\,000$). Each of the next $N$ lines contains two integers $x$ and $y$, meaning that Farmer John has $x$ cows, each with milk output $y$ ($1 \le y \le 1\,000\,000\,000$). The sum of all $x$ values is $M$, the total number of cows.

Print the minimum amount of time it takes to milk all the cows, assuming they are paired up optimally.

In the sample, if the cows with outputs 8 and 2 are paired up, and the two cows with output 5 are paired up, both stalls take 10 units of time for milking. Since milking takes place simultaneously, the entire process completes after 10 units of time. Any other pairing is sub-optimal, because some stall would take more than 10 units of time.