Олимпиадный тренинг

Задача 27220. paired up


Farmer John has discovered that it is easier to milk a cow if there is another cow nearby for moral support. So he wants to break M of his cows (M <= 109, M - even ) to M/2 par. He places each of these pairs in a separate stall, and all pairs of cows are milked at the same time.
Each cow gives a different amount of milk. If cows in a pair produce A and B liters of milk, then milking this pair requires A+B units of time.
Help the FD determine the minimum amount of time possible for the entire milking process, assuming cows are best paired.
 
 
Input
The first input line contains N (1 <= <= 100000). Each of the following N lines contains two integers x and y indicating that the FD has x  cows with milk production of y (1 <= y <= 109) liters. The sum of all x's is M- the total number of cows.

Output
Print the minimum amount of time it will take to milk all the cows, assuming they are optimally paired.

 
Examples
# Input Output
1
3
18
2 5
1 2
10