Two-Machine Flow Shop Scheduling

A factory has received orders for $n$ products. Each product must be processed first in workshop A and then in workshop B. For each product i, the processing times in workshop A and B are given as $A_i$ and $B_i$, respectively. The processing of a product in workshop B can only start after its processing in workshop A is complete.

The total processing time is defined as the time elapsed from the start of processing the first product in workshop A to the completion of processing the last product in workshop B. You are required to determine an optimal processing order for the n products that minimizes the total processing time.

This problem can be solved using Johnson's rule. Specifically, partition the products into two sets:

• Set 1: products for which $A_i \leq B_i$. Sort these in ascending order of $A_i$.
• Set 2: products for which $A_i > B_i$. Sort these in descending order of $B_i$.

Then, the optimal processing order is the concatenation of Set 1 followed by Set 2. The total processing time is computed by simulating the processing in both workshops sequentially: at each step, update the completion times of workshop A and workshop B.

inputFormat

The first line contains an integer n representing the number of products.

Each of the following n lines contains two integers A_i and B_i, separated by a space, denoting the processing times for product i in workshops A and B respectively.

outputFormat

Output a single integer representing the minimal total processing time to process all products in the optimal order.

sample

3
3 5
2 1
4 3

12