Maximizing Trading Profit on Beijing Road Pedestrian Street

In Guangzhou’s famous Beijing Road Pedestrian Street there are n stores trading a certain product. Each store has its own trading price, and both buying and selling occur at the same price in that store. The i-th store has a price of \(a_i\) and a trading limit of \(b_i\) (each buy or sell counts separately toward this limit, and you may only trade one product per operation).

You start with an infinite amount of money and wish to make a profit by buying the product at some stores and selling at others. The profit from one transaction is defined as the selling price minus the buying price. Note that you cannot exceed the trading limit at any store; if you perform a buy or a sell, that counts as one trade at that store. Also, a store used for both buying and selling must have its total operations (buying plus selling) not exceeding \(b_i\).

Your goal is to maximize your total profit, which is the sum of the money received from selling minus the money spent on buying. Formally, if you buy \(x_i\) products in store \(i\) (spending \(a_i\) each) and sell \(y_i\) products in store \(i\) (earning \(a_i\) each), with the constraints

[ \begin{aligned} &x_i \ge 0, \quad y_i \ge 0,\ &x_i + y_i \le b_i \quad \text{for } i=1,2,\ldots,n,\ &\sum_{i=1}^n x_i = \sum_{i=1}^n y_i = T \quad \text{(total number of products traded)}, \end{aligned} ]

and the total number of trades used is at most \(\sum_{i=1}^n b_i\). Since each product transaction uses one trade when buying and one trade when selling, the maximum possible total transactions is \(T = \lfloor (\sum_{i=1}^n b_i)/2 \rfloor\). The overall profit is

[ \text{Profit} = \sum_{i=1}^n a_i \cdot y_i - \sum_{i=1}^n a_i \cdot x_i. ]

To maximize your profit, it is optimal to buy as much as possible in the cheaper stores and sell as much as possible in the more expensive stores while respecting each store's trade limit. One valid approach is:

1. Set \(T = \lfloor (\sum_{i=1}^n b_i)/2 \rfloor\).
2. Sort the stores by increasing \(a_i\) and allocate the buying operations greedily: for each store in this order, buy \(\min(b_i, \text{remaining})\) items until you have bought \(T\) items in total.
3. Sort the stores by decreasing \(a_i\) and allocate the selling operations greedily: for each store in this order, sell \(\min(b_i, \text{remaining})\) items until you have sold \(T\) items in total.
4. If a store is used in both buying and selling, note that the sum of operations for that store does not exceed \(b_i\); this is guaranteed because \(2T \le \sum b_i\).
5. Compute the total profit as the total revenue from sales minus the total cost from purchases.

Your task is to implement a program that, given \(n\) and for each store the pair \(a_i\) and \(b_i\), computes the maximum possible profit.

inputFormat

The first line contains a single integer \(n\) (the number of stores).

Each of the following \(n\) lines contains two integers \(a_i\) and \(b_i\) separated by a space, representing the trading price and the trading limit for the \(i\)-th store.

\(1 \le n \le 10^5\), \(1 \le a_i, b_i \le 10^9\).

outputFormat

Output a single integer — the maximum profit that can be achieved.

sample

3
3 3
5 3
10 4

26