Das drahtlose Telekommunikationsunternehmen KOI möchte Basisstationen auf einer geraden Kommunikationslinie aufstellen, sodass alle wichtigen Gebäude in der Umgebung in ihrem Abdeckungsbereich liegen. Der Abdeckungsbereich jeder Station ist ein Quadrat mit der Station als Mittelpunkt und einer zur Kommunikationslinie parallelen Grundseite. Die Seitenlänge dieses Quadrats heißt Kommunikationsbreite. Die gesamten Installationskosten sind die Summe der Kommunikationsbreiten aller Stationen und hängen nicht von deren Anzahl ab.

Gegeben sind die Positionen wichtiger Gebäude in der Ebene. Schreibe ein Programm, das die geringsten gesamten Installationskosten für Basisstationen bestimmt, deren Abdeckung alle wichtigen Gebäude umfasst. Die Kommunikationslinie stimmt mit der $x$-Achse überein, und die Gebäudekoordinaten sind ganzzahlig. Kein Gebäude liegt auf der Kommunikationslinie, und alle Gebäude haben unterschiedliche Positionen.

Im Beispiel der folgenden Abbildung gilt:

(1) Die erste Basisstation liegt bei $(-2, 0)$; ihre quadratische Abdeckung mit Kommunikationsbreite 4 umfasst drei Gebäude.

(2) Die zweite Basisstation liegt bei $(2, 0)$; ihre quadratische Abdeckung mit Kommunikationsbreite 2 umfasst zwei Gebäude.

(3) Die dritte Basisstation liegt bei $(6.5, 0)$; ihre quadratische Abdeckung mit Kommunikationsbreite 3 umfasst zwei Gebäude.

Eingabe

Die erste Zeile enthält die Anzahl der Gebäude $N$ ($1\le N\le 10{,}000$). Jede der nächsten $N$ Zeilen enthält die $x$-Koordinate und danach die $y$-Koordinate eines Gebäudes, getrennt durch ein Leerzeichen. Beide Koordinaten sind ganze Zahlen mit einem Absolutwert von höchstens $1{,}000{,}000$.

Ausgabe

Gib in der ersten Zeile die geringsten gesamten Installationskosten aus (die Summe der Kommunikationsbreiten, welche die Abdeckung der Basisstationen beschreiben).

Beispiele

Eingabe 1

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

Ausgabe 1

9