A empresa de comunicações sem fio KOI deseja instalar estações-base em uma linha reta de comunicação para que todos os edifícios importantes próximos estejam dentro da cobertura. A cobertura de cada estação é um quadrado centrado na estação, com a base paralela à linha de comunicação. O comprimento do lado desse quadrado é chamado de largura de comunicação. O custo total de instalação é a soma das larguras de comunicação das estações, independentemente do número de estações.

Dadas as posições dos edifícios importantes no plano, escreva um programa para encontrar o menor custo total de instalação de estações cuja cobertura inclua todos os edifícios importantes. A linha de comunicação coincide com o eixo $x$, e as coordenadas dos edifícios são inteiras. Nenhum edifício está na linha de comunicação, e todas as posições são distintas.

No exemplo da figura a seguir:

(1) A primeira estação-base está em $(-2, 0)$, e sua cobertura quadrada com largura de comunicação 4 inclui três edifícios.

(2) A segunda estação-base está em $(2, 0)$, e sua cobertura quadrada com largura de comunicação 2 inclui dois edifícios.

(3) A terceira estação-base está em $(6.5, 0)$, e sua cobertura quadrada com largura de comunicação 3 inclui dois edifícios.

Entrada

A primeira linha contém o número de edifícios $N$ ($1\le N\le 10{,}000$). Cada uma das próximas $N$ linhas contém a coordenada $x$ e depois a coordenada $y$ de um edifício, separadas por um espaço. Ambas as coordenadas são inteiros com valor absoluto de no máximo $1{,}000{,}000$.

Saída

Imprima na primeira linha o menor custo total de instalação (a soma das larguras de comunicação que descrevem a cobertura das estações-base).

Exemplos

Entrada 1

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

Saída 1

9