Paired Up#10524
Farmer John has found that his cows are easier to milk when they have another cow nearby for moral support. He therefore wants to take his cows (m \le 10^9, is even) and divide them into pairs. Each pair of cows will then be taken to a separate stall in the barn for milking. Milking in all stalls will take place simultaneously.
To make matters a bit more complicated, each of Farmer John's cows produces a different amount of milk. If cows with milk outputs and are paired together, it takes a total of a + b units of time to milk them both.
Please help Farmer John determine the minimum possible amount of time needed to milk all of his cows, assuming he pairs them in the best possible way.
The first line contains n~(1 \le n \le 10^5). Each of the next lines contains two integers and , indicating that FJ has cows, each with milk output y~(1 \le y \le 10^9). The sum of the 's is , the total number of cows. It is guaranteed that is even.
Print the minimum amount of time needed to milk all of FJ's cows, assuming they are paired optimally.
Suppose, for example, that cows with milk outputs and are paired together, while two cows with milk output are paired together. Both stalls would then take units of time to complete the milking. Since all milking takes place simultaneously, the entire process would therefore be completed in units of time.
Any other pairing would be suboptimal, resulting in at least one stall taking more than units of time.
Example 1