Paired Up

Interview

Time limit2sMemory limit512 MB

Summary

Pair up M cows with given milk outputs to minimize the maximum sum in any pair, where each pair's time is A+B. Input gives counts and output values in compressed form.

Level: Medium6 of 10
Topics: Greedy, Two pointers, Sorting, Math
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Hint

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.

Examples1

Example 1
Input
```
3
1 8
2 5
1 2
```
Expected output
```
10
```