Descripcion

El Sr. OCI tiene un enorme escritorio en su sala de colecciones, y sobre él hay varias monedas raras. Para limpiar el escritorio, va a reorganizar las monedas.

El escritorio se puede considerar como una cuadrícula de ~2 000 000 001~ × ~2 000 000 001~. Las columnas están numeradas de ~-1 000 000 001~ × ~2 000 000 001~ de izquierda a derecha, y las filas están numeradas de ~-1 000 000 000~ a ~1 000 000 000~ de abajo a arriba. La celda con el número de columna ~x~ y el número de fila ~y~ se denomina por (~x~, ~y~).

Hay ~2N~ monedas. Actualmente, la moneda i-ésima (~1 \le i \le 2N~) se coloca en la celda (~X_i~, ~Y_i~). El objetivo del Sr. OCI es colocar una moneda en cada celda (~x~, ~y~) con ~1 \le x \le N~ y ~1 \le y \le 2~. Para no dañar las monedas, la única operación que puede realizar es elegir una moneda y moverla a una de las celdas vecinas (una celda es vecina de otra si y sólo si comparten una arista). Se permite que varias monedas se coloquen en una celda en algún momento. Quiere alcanzar el objetivo con el menor número de operaciones posible.

Tarea

Escriba un programa que, dado el número de monedas y las celdas donde están colocadas actualmente las monedas, calcule el mínimo número de operaciones necesarias para alcanzar el objetivo.

Entrada

Lee los siguientes datos de la entrada estándar.

~N~

~X_1~ ~Y_1~

...

~X_{2N}~ ~Y_{2N}~

Salida

Escriba una línea en la salida estándar. La salida debe contener el número mínimo de operaciones necesarias para alcanzar el objetivo.

Restricciones

• ~1 \le N \le 100 000~.
• ~-1 000 000 000 \le X_i \le 1 000 000 000~ (~1 \le i \le 2N~).
• ~-1 000 000 000 \le Y_i \le 1 000 000 000~ (~1 \le i \le 2N~).

Subtareas

1. (8 points) ~N \le 10~.
2. (29 points) ~N \le 1 000~.
3. (63 points) No additional constraints.

Ejemplos de Entrada y Salida

Ejemplo de Entrada #1

3
0 0
0 4
4 0
2 1
2 5
-1 1

Ejemplo de Salida #1

15

En esta entrada de ejemplo, se colocan ~6~ monedas como en la figura de abajo. El objetivo es recoger las monedas dentro de las líneas gruesas.

Se pueden colocar varias monedas en una celda

Por ejemplo, el Sr. OCI puede lograr el objetivo con 15 operaciones mediante los siguientes movimientos:

• La 1ª moneda: (0, 0) → (1, 0) → (1, 1) → (1, 2)
• La 2ª moneda: (0, 4) → (1, 4) → (1, 3) → (2, 3) → (3, 3) → (3, 2)
• La 3ª moneda: (4, 0) → (4, 1) → (3, 1)
• La 5ª moneda: (2, 5) → (2, 4) → (2, 3) → (2, 2)
• La 6ª moneda: (-1, 1) → (0, 1) → (1, 1)

Como no puede alcanzar el objetivo con ~14~ o menos operaciones, debes dar ~15~.

Ejemplo de Entrada #2

4
2 1
2 1
2 1
3 1
3 1
3 1
3 1
3 1

Ejemplo de Salida #2

9

Se pueden colocar varias monedas en una casilla

Ejemplo de Entrada #3

5
1000000000 1000000000
-1000000000 1000000000
-1000000000 -1000000000
1000000000 -1000000000
-1 -5
-2 2
2 8
4 7
-2 5
7 3

Ejemplo de Salida #3

8000000029