L'entreprise de communications sans fil KOI souhaite installer des stations de base sur une ligne de communication droite afin que tous les bâtiments importants alentour soient couverts. La couverture de chaque station est un carré centré sur celle-ci, dont la base est parallèle à la ligne de communication. La longueur d'un côté de ce carré est appelée largeur de communication. Le coût total d'installation est la somme des largeurs de communication des stations, indépendamment de leur nombre.

Étant données les positions des bâtiments importants dans le plan, écrivez un programme qui détermine le coût total minimal d'installation de stations couvrant tous les bâtiments importants. La ligne de communication coïncide avec l'axe $x$, et les coordonnées des bâtiments sont entières. Aucun bâtiment ne se trouve sur la ligne de communication, et toutes leurs positions sont distinctes.

Dans l'exemple de la figure suivante :

(1) La première station de base est située en $(-2, 0)$, et sa couverture carrée de largeur de communication 4 contient trois bâtiments.

(2) La deuxième station de base est située en $(2, 0)$, et sa couverture carrée de largeur de communication 2 contient deux bâtiments.

(3) La troisième station de base est située en $(6.5, 0)$, et sa couverture carrée de largeur de communication 3 contient deux bâtiments.

Entrée

La première ligne contient le nombre de bâtiments $N$ ($1\le N\le 10{,}000$). Chacune des $N$ lignes suivantes contient la coordonnée $x$, puis la coordonnée $y$ d'un bâtiment, séparées par un espace. Ces coordonnées sont des entiers de valeur absolue au plus $1{,}000{,}000$.

Sortie

Affichez sur la première ligne le coût total minimal d'installation (la somme des largeurs de communication décrivant la couverture des stations de base).

Exemples

Entrée 1

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

Sortie 1

9