La empresa de comunicaciones inalámbricas KOI desea instalar estaciones base en una línea recta de comunicación para cubrir todos los edificios importantes cercanos. La cobertura de cada estación es un cuadrado centrado en ella, cuya base es paralela a la línea de comunicación. La longitud de un lado de ese cuadrado se llama ancho de comunicación. El coste total de instalación es la suma de los anchos de comunicación de las estaciones, independientemente del número de estaciones.

Dadas las posiciones de los edificios importantes en el plano, escribe un programa que encuentre el coste total mínimo de instalar estaciones que cubran todos los edificios importantes. La línea de comunicación coincide con el eje $x$, y las coordenadas de los edificios son enteras. Ningún edificio se encuentra en la línea de comunicación, y todas las posiciones son distintas.

En el ejemplo de la siguiente figura:

(1) La primera estación base está en $(-2, 0)$ y su cobertura cuadrada de ancho de comunicación 4 incluye tres edificios.

(2) La segunda estación base está en $(2, 0)$ y su cobertura cuadrada de ancho de comunicación 2 incluye dos edificios.

(3) La tercera estación base está en $(6.5, 0)$ y su cobertura cuadrada de ancho de comunicación 3 incluye dos edificios.

Entrada

La primera línea contiene el número de edificios $N$ ($1\le N\le 10{,}000$). Cada una de las siguientes $N$ líneas contiene la coordenada $x$ y luego la coordenada $y$ de un edificio, separadas por un espacio. Ambas coordenadas son enteros de valor absoluto no mayor que $1{,}000{,}000$.

Salida

Imprime en la primera línea el coste total mínimo de instalación (la suma de los anchos de comunicación que describen la cobertura de las estaciones base).

Ejemplos

Entrada 1

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

Salida 1

9