Problem Description

Given $n$ pairs $(a_i, b_i)$.

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

Find a Hamiltonian cycle in $G$ that maximizes the sum of the weights of the edges it traverses, and output this maximum value.

Input Format

The first line contains an integer $n (2 \le n \le 10^5)$, representing the number of pairs. The next $n$ lines each contain two integers $a_i, b_i \ (0 \le a_i, b_i \le 10^9)$, representing each pair. It is guaranteed that among the $2n$ numbers in the $n$ pairs, all numbers are pairwise distinct.

Output Format

Output one integer on a single line, representing the maximum total edge weight of a Hamiltonian cycle.

3
1 10
8 2
4 5

10

Hint

Consider the Hamiltonian cycle $1 \to 2 \to 3 \to 1$. The sum of edge weights is $|1 - 2| + | 8 - 5| + |4 - 10| = 10$. It can be proven that no Hamiltonian cycle has a total edge weight exceeding $10$, so the answer is $10$.

Translated by ChatGPT 5