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 <= N <= 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 |