Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.
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)$$$ 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?
Input
The first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).
The $$$i$$$-th of the next $$$2n$$$ lines contain 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 the matching in this graph.