E. Duas faixas

Time limit: 3000 msMemory limit: 256 MB

Há $n$ pontos no plano. Você deve escolher uma faixa vertical $L \le x \le R$ e uma faixa horizontal $B \le y \le T$ , de forma que cada ponto pertença a pelo menos uma das faixas.

As quatro bordas podem ter coordenadas reais. As faixas incluem suas bordas, são ilimitadas na outra direção e podem ter largura zero. Não é necessário que cada faixa cubra algum ponto.

Minimize a soma das larguras $(R-L)+(T-B)$ . O valor mínimo é sempre inteiro; imprima esse inteiro.

Input

A primeira linha contém $n$ ( $1 \le n \le 200\,000$ ). Cada uma das próximas $n$ linhas contém as coordenadas inteiras $x_i,y_i$ (). Pontos coincidentes são permitidos.

Output

Imprima a menor soma possível das larguras.

Samples

Sample 1

Input

Output

Uma faixa vertical de x=0 até x=4 cobre todos os pontos. A faixa horizontal pode ter largura zero. Não é possível obter soma menor que 4.

Sample 2

Input

Output

Escolha a faixa vertical de x=4 até x=5 e a horizontal de y=0 até y=1. A soma das larguras é 2, que é mínima.