Max Pair Matching

Time limit1sMemory limit1024 MB

Summary

Given 2n pairs (a_i, b_i), find a perfect matching that maximizes the total of max(|a_i-a_j|, |a_i-b_j|, |b_i-a_j|, |b_i-b_j|) over matched pairs, and print that sum.

Level: Medium6 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Problem

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

Determine the maximum weight of a matching in this graph. That is, choose $n$ edges so that no two chosen edges share an endpoint, and find the largest possible total weight of those edges.

Input

The first line contains a single integer $n$ ( $1 \le n \le 10^5$ ).

Each of the next $2n$ lines contains two integers $a_i$ and $b_i$ ( $0 \le a_i, b_i \le 10^9$ ).

Output

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

Hint

The adjacency matrix is:

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

Examples1

Example 1
Input
```
2
0 10
7 7
9 4
2 15
```
Expected output
```
18
```