P6243 [USACO06OPEN] The Milk Queue G

This problem is a shortened version that ensures the original meaning is not changed.

Every morning, Farmer John’s $N$ cows line up to be milked. They enter the barn one by one. To improve efficiency, Farmer John splits the whole milking process into two steps: FJ performs the first step, and the second step is done by Rob. If one cow starts the first step earlier than another cow, then she will also start the second step earlier. FJ noticed that if the cows line up in a certain order, they may spend a lot more time waiting in line. For example, if FJ needs a long time to finish the first step for a certain cow, then Rob will waste some time. On the other hand, if FJ finishes too quickly, a long queue of cows will form in front of Rob. Please compute the minimum total time needed to finish milking if the cows are queued in the best possible order. For each cow, the input provides the time $A_i$ for the first step and the time $B_i$ for the second step.

The first line contains an integer $N$. The next $N$ lines each contain two integers, representing $A_i$ and $B_i$ for the $i$-th cow.

Output the shortest time required to finish milking after arranging the queue in the optimal order.

#### Sample Explanation Arrange the cows in the order $3, 1, 2$. In this way, the whole milking process takes a total of 16 units of time. $1 \le N \le 25000$ $1 \le A_i, B_i \le 2 \times 10^4$ 2025-06-03: Added one set of hack testdata. Translated by ChatGPT 5