Maximum Revenue from Selling Items

Alice has \(2n\) items. Two buyers, Bob and Charlie, are interested in buying these items. For the \(i^{th}\) item, Bob is willing to pay \(b_i\) and Charlie is willing to pay \(c_i\). However, to split the items evenly, exactly \(n\) items must be sold to Bob and the remaining \(n\) items to Charlie.

Your task is to help Alice determine the maximum revenue he can obtain by selling all \(2n\) items under these constraints.

Hint: Consider selecting the items for Bob in such a way that the difference \(d_i = b_i - c_i\) is maximized. In other words, if we initially assign all items to Charlie, the revenue is \(\sum_{i=1}^{2n} c_i\). Then, by transferring an item to Bob, the revenue increases by \(b_i - c_i\). Sort the items by \(d_i\) in descending order and choose the top \(n\) items to transfer to Bob.

inputFormat

The input consists of multiple lines:

1. The first line contains a single integer \(n\) (where \(1 \leq n \leq 10^5\)).
2. The next \(2n\) lines each contain two space-separated integers \(b_i\) and \(c_i\) (\(1 \leq b_i, c_i \leq 10^9\)), representing the price Bob and Charlie will pay for the \(i^{th}\) item respectively.

outputFormat

Output a single integer, the maximum revenue Alice can achieve.

sample

1
3 2
1 4

7