Farmer John hat $N$ Heuballen, $(1 \le N \le 50,000)$, in der Mitte eines seiner Felder angeordnet. Wenn wir das Feld als ein Gitter aus $1,000,000$ $x$ $1,000,000$ quadratischen Zellen der Größe $1$ $x$ $1$ betrachten, belegt jeder Heuballen genau eine Zelle (natürlich belegen keine zwei Ballen dieselbe Zelle).

FJ bemerkt, dass alle Heuballen ein einziges großes zusammenhängendes Gebiet bilden: Von jedem Ballen aus kann man jeden anderen erreichen, indem man schrittweise nach Norden, Süden, Osten oder Westen auf direkt benachbarte Ballen geht. Das Gebiet kann allerdings „Löcher“ enthalten, also leere Gebiete, die vollständig von Heuballen umgeben sind.

Hilf FJ, den Umfang des von seinen Heuballen gebildeten Gebiets zu bestimmen. Löcher tragen nicht zum Umfang bei.

Eingabe

• Zeile 1: die Anzahl der Heuballen, $N$.

• Die nächsten $N$ Zeilen, also die Zeilen $2\ldots1+N$: Jede Zeile enthält die Position ($x$, $y$) eines Heuballens; $x$ und $y$ sind ganze Zahlen im Bereich $1\ldots1,000,000$. Die Position $(1,1)$ ist die untere linke Zelle des Feldes, und $(1000000,1000000)$ die obere rechte.

Ausgabe

• Zeile 1: der Umfang des zusammenhängenden Gebiets der Heuballen.

Beispiele

Eingabe 1

8
10005 200003
10005 200004
10008 200004
10005 200005
10006 200003
10007 200003
10007 200004
10006 200005

Ausgabe 1

14

Hinweis

Das zusammenhängende Gebiet der Heuballen sieht so aus:

XX 
X XX
XXX

Der Umfang des Gebiets beträgt $14$ (zum Beispiel trägt die linke Seite eine Länge von $3$ zum Gesamtwert bei). Das Loch in der Mitte trägt nicht zu diesem Wert bei.

Autor der Aufgabe: Brian Dean, 2013