Cabos na avenida

Time limit: 3000 msMemory limit: 256 MB

Há $n$ torres em posições distintas $x_i$ de uma avenida reta, cada uma com altura $h_i$ . É possível instalar um cabo entre qualquer par de torres $i,j$ . O preço cobrado é

$|x_i-x_j|+\max(h_i,h_j).$

A primeira parcela corresponde à distância ao longo da avenida; a segunda, ao equipamento necessário para trabalhar na torre mais alta.

Escolha cabos para que todas as torres fiquem conectadas, possivelmente por caminhos com vários cabos, minimizando o preço total. Cabos podem se cruzar ou passar por outras torres sem se conectar a elas: somente suas extremidades determinam a conexão.

Input

A primeira linha contém $n$ ( $1\le n\le200\,000$ ).

Cada uma das próximas $n$ linhas contém $x_i$ e (, ). As posições são distintas e não necessariamente estão ordenadas.

Output

Imprima o menor preço total. Para uma única torre, o preço é zero.

Samples

Sample 1

Input

Output

Ligue as duas torres externas por $11$ e ligue a torre central a uma delas por $105$ , totalizando $116$ .

Sample 2

Input

1
7 9

Output

Nenhum cabo é necessário.

Sample 3

Input

Output

Ligar torres consecutivas custa $6+7=13$ .