Hamiltonian Circuit

You are given $n$ pairs of integers $(a_i, b_i)$.

Consider a weighted directed complete graph $G$ with $n$ vertices, where the weight of the edge from $i$ ($1 \leq i \leq n$) to $j$ ($1 \leq j \leq n$) is $|a_i - b_j|$.

Find a Hamiltonian circuit in $G$ whose total edge weight is maximized, and print this maximum value.

The first line contains an integer $n$ ($2 \leq n \leq 10^5$), the number of pairs.

Each of the next $n$ lines contains two integers $a_i$ and $b_i$ ($0 \leq a_i, b_i \leq 10^9$), describing one pair.

You may assume that all $2n$ integers $a_i$ and $b_i$ are pairwise distinct.

Print a single integer on one line: the maximum total weight of a Hamiltonian circuit.

Take the circuit $1 \to 2 \to 3 \to 1$ in the example. Its edge weights are $|1-2| + |8-5| + |4-10| = 10$. No Hamiltonian circuit has a total weight above 10, so the answer is 10.