H. Redes
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Resulta que la vida laboral es justo como la escuela, pero aún peor. Ahora en lugar de conectar routers en un salón de clase tu trabajo es conectar un montón de routers repartidos a través de una ciudad con calles perféctamente cuadradas. Para ello tienes que conectarlos con fibra óptica a través de postes y vías subterráneas; para propósitos prácticos supongamos que no importa por dónde los metas entre esas dos, pero lo importante es que no los metas a través de manzanas. Para tu conveniencia los routers siempre estarán en las esquinas de las manzanas.

Igual que en la escuela, lo importante es pasar. En este caso eso significa solo conectar los routers; redundancia y cosas por el estilo no importan.

Input

Un número N, el número de routers a conectar.

En las siguientes N líneas, N pares de números xi, yi representando cada una de las coordenadas de los routers.

Output

La mínima longitud de cable necesaria para conectar todos los routers.

Example
Input
3
5 7
1 1
2 8
Output
12
Note
  • 1 ≤ N ≤ 105
  •  - 231 < xi, yi < 231

Se puede conectar el router en la posición (1, 1) con el de la posición (2,8); estos están a distancia 8. Luego conectamos el (2, 8) con el (5, 7), y estos 2 están a dsitancia 4. La distancia total es 8 + 4 = 12.