33423번 - 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$ such that the sum of weights of the edges it traverses is maximized, and output this maximum value.

The first line of the input contains an integer $n$ ($2 \leq n \leq 10^5$) representing 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$) representing a single pair.

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

Print a line with a single integer: the maximum sum of weights of the Hamiltonian circuit.

In the example, consider the Hamiltonian circuit $1 \to 2 \to 3 \to 1$, with edge weights $|1-2| + |8-5| + |4-10| = 10$. It can be proven that there is no Hamiltonian circuit with sum of weights exceeding $10$, so the answer is $10$.