31159번 - Max Pair Matching 다국어

문제

You are given 2ドルn$ pairs $(a_i, b_i)$ of integers. Consider a complete graph on 2ドルn$ vertices and define the weight of the edge $(ij)$ to be $w_{ij} = max(|a_i-a_j|, |a_i-b_j|, |b_i-a_j|, |b_i-b_j|)$.

Determine the maximum weight of the matching in this graph.

In other words, consider all ways to select $n$ edges of this graph such that no two chosen edges have a common endpoint. What is the maximum possible total weight of these edges?

입력

The first line of the input contains a single integer $n$ (1ドル \le n \le 10^5$).

The $i$-th of the next 2ドルn$ lines contain two integers $a_i$ and $b_i$ (0ドル \le a_i, b_i \le 10^9$).

출력

Print a single integer --- the maximum weight of the matching in this graph.

제한

노트

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