Se te dan $2n$ pares de enteros $(a_i,b_i)$. Considera un grafo completo de $2n$ vértices y define el peso de la arista $(ij)$ como $w_{ij}=\max(|a_i-a_j|,|a_i-b_j|,|b_i-a_j|,|b_i-b_j|)$.
Determina el peso máximo de un emparejamiento en este grafo.
En otras palabras, considera todas las formas de elegir $n$ aristas de este grafo de modo que no haya dos aristas elegidas con un extremo en común. ¿Cuál es el máximo peso total posible de estas aristas?
Entrada
La primera línea de la entrada contiene un entero $n$ ($1\le n\le 10^5$).
La $i$-ésima de las siguientes $2n$ líneas contiene dos enteros $a_i$ y $b_i$ ($0\le a_i,b_i\le 10^9$).
Salida
Imprime un entero: el peso máximo de un emparejamiento en este grafo.
Ejemplos
Entrada 1
2 0 10 7 7 9 4 2 15
Salida 1
18
Nota
Matriz de adyacencia: $$\begin{matrix}0&7&9&15\\7&0&3&8\\9&3&0&11\\15&8&11&0\end{matrix}$$