無線通信会社 KOI は、直線状の通信線上に基地局を設置し、周辺の重要な建物をすべて通信範囲に含めたいと考えています。各基地局の通信範囲は、基地局を中心とし、底辺が通信線に平行な正方形です。この正方形の一辺の長さを通信幅と呼びます。基地局の総設置費用は各基地局の通信幅の合計であり、基地局の数には依存しません。

平面上の重要な建物の位置が与えられたとき、基地局を設置してすべての重要な建物を通信範囲に含めるための最小の総設置費用を求めるプログラムを作成してください。通信線は $x$ 軸と一致し、建物の位置座標は整数です。通信線上に建物はなく、すべての建物の位置は互いに異なります。

次の図の例では、以下のようになります。

(1) 1 番目の基地局の位置は $(-2, 0)$ で、通信幅 4 の正方形の通信範囲に 3 棟の建物を含みます。

(2) 2 番目の基地局の位置は $(2, 0)$ で、通信幅 2 の正方形の通信範囲に 2 棟の建物を含みます。

(3) 3 番目の基地局の位置は $(6.5, 0)$ で、通信幅 3 の正方形の通信範囲に 2 棟の建物を含みます。

入力

1 行目に建物の数 $N$（$1\le N\le 10{,}000$）が与えられます。続く $N$ 行には、1 行に 1 棟の建物の $x$ 座標と $y$ 座標がこの順に空白区切りで与えられます。両座標は絶対値が $1{,}000{,}000$ 以下の整数です。

出力

最小の総設置費用（基地局の通信範囲を表す通信幅の合計）を 1 行目に出力してください。

入出力例

入力 1

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

出力 1

9