Mountain Climbing Cows

Farmer John has discovered that his cows produce higher quality milk when they are subject to strenuous exercise. He therefore decides to send his N cows to climb up and then back down a nearby mountain! Each cow i takes \(U(i)\) time to climb up and \(D(i)\) time to climb down the mountain. Since each cow needs the help of a guide for each leg of the climb and there is only one available guide for each (Farmer John for the up-climb and Farmer Don for the down-climb), at most one cow can be climbing upward or downward at any time. Cows may wait at the top of the mountain and can descend in a different order than they ascended.

The task is to determine the least possible amount of time for all cows to complete their journey. This problem can be modeled as a two-machine flow shop scheduling problem, and the optimal order can be found using Johnson's rule. Specifically, partition the cows into two groups: those with \(U(i) \le D(i)\) (which are scheduled first, in ascending order of \(U(i)\)) and those with \(U(i) > D(i)\) (which are scheduled later, in descending order of \(D(i)\)). The minimal finishing time is then obtained by simulating the process in this order.

inputFormat

The first line of input contains an integer \(N\) (\(1 \le N \le 25000\)), representing the number of cows. Each of the following \(N\) lines contains two space-separated integers: \(U(i)\) and \(D(i)\), representing the times for the upward and downward climbs, respectively.

outputFormat

Output a single integer representing the minimum total time for all cows to complete the mountain climbing journey.

sample

3
6 4
8 1
2 3

17