최대 쌍 매칭

정수 쌍 $(a_i, b_i)$가 $2n$개 주어진다. 정점이 $2n$개인 완전 그래프를 생각하고, 간선 $(ij)$의 가중치를 $w_{ij} = max(|a_i-a_j|, |a_i-b_j|, |b_i-a_j|, |b_i-b_j|)$로 정의한다.

이 그래프의 매칭 가중치 최댓값을 구하라. 즉, 두 간선이 끝점을 공유하지 않도록 간선 $n$개를 고르고, 고른 간선 가중치의 합이 가장 클 때의 값을 구한다.

첫째 줄에 정수 $n$ ($1 \le n \le 10^5$)이 주어진다.

이어지는 $2n$개의 줄에 정수 $a_i$와 $b_i$ ($0 \le a_i, b_i \le 10^9$)가 각각 주어진다.

이 그래프에서 매칭 가중치의 최댓값을 정수 하나로 출력한다.

인접 행렬은 다음과 같다.

$\begin{matrix}0 & 7 & 9 & 15 \\ 7 & 0 & 3 & 8 \\ 9 & 3 & 0 & 11 \\ 15 & 8 & 11 & 0 \end{matrix}$