Problembeschreibung

Ende letzten Jahres hat der Weihnachtsmann vergessen, den Kindern im Dorf JOI Weihnachtsgeschenke zu bringen. Als Entschuldigung beschloss er daher, den Kindern Schokoladenkuchen zu liefern. Da der Liefertag schon morgen ist, muss er sich bald einen Bewegungsplan überlegen.

Das Dorf JOI ist durch $W$ gerade Straßen in Nord-Süd-Richtung und $H$ gerade Straßen in Ost-West-Richtung schachbrettartig unterteilt. Die $W$ Straßen in Nord-Süd-Richtung sind von Westen her der Reihe nach mit $1, 2, \dots, W$ nummeriert, und die $H$ Straßen in Ost-West-Richtung sind von Süden her der Reihe nach mit $1, 2, \dots, H$ nummeriert. Die Kreuzung, an der sich die $x$-te Nord-Süd-Straße von Westen und die $y$-te Ost-West-Straße von Süden treffen, wird mit $(x, y)$ bezeichnet. Im Dorf JOI gibt es $N$ Häuser, die sich jeweils an einer der Kreuzungen befinden. Der Weihnachtsmann kann sich nur entlang der Straßen bewegen. Die Zeit, die benötigt wird, um sich zwischen benachbarten Kreuzungen zu bewegen, beträgt $1$.

Da es in allen Häusern im Dorf JOI Kinder gibt, muss der Weihnachtsmann alle Häuser im Dorf JOI besuchen und jedem Haus $1$ Schokoladenkuchen bringen. Da es etwas gefährlich ist, mit den wertvollen Schokoladenkuchen und den Rentieren durch die Luft zu fliegen, landen der Weihnachtsmann und die Rentiere an einer Kreuzung im Dorf JOI, und der Weihnachtsmann liefert die Schokoladenkuchen von dort aus zu Fuß aus. Der Weihnachtsmann trägt beim Gehen niemals $2$ oder mehr Schokoladenkuchen gleichzeitig. Das heißt, jedes Mal, wenn der Weihnachtsmann $1$ Haus einen Schokoladenkuchen geliefert hat, kehrt er zu der Kreuzung zurück, an der er gelandet ist.

Der Weihnachtsmann hat beschlossen, einen Bewegungsplan zu wählen, bei dem die benötigte Gesamtzeit von der Landung im Dorf JOI bis zur Auslieferung der Schokoladenkuchen an alle Häuser minimal ist. Beachte hierbei, dass die Zeit für den Rückweg zur Landekreuzung nach der Auslieferung des Schokoladenkuchens an das letzte Haus nicht zur benötigten Zeit gezählt wird. Außerdem wird nichts anderes als die für die Bewegung benötigte Zeit berücksichtigt.

Schreibe ein Programm, das anhand der Informationen über die Standorte der Häuser das Minimum der benötigten Zeit von der Landung im Dorf JOI bis zur Auslieferung der Schokoladenkuchen an alle Häuser bei optimaler Wahl der Landekreuzung sowie die Position der Kreuzung bestimmt, an der der Weihnachtsmann landen sollte, um die benötigte Zeit zu minimieren.

Eingabe

Lies die folgende Eingabe von der Standardeingabe:

• Die $1$. Zeile enthält durch ein Leerzeichen getrennt die ganzen Zahlen $W, H$, die die Anzahl der Straßen in jeder Richtung angeben.
• Die $2$. Zeile enthält eine ganze Zahl $N$, die die Anzahl der Häuser angibt.
• Die folgenden $N$ Zeilen enthalten Informationen über die Standorte der Häuser. Die $(i + 2)$. Zeile ($1 \le i \le N$) enthält durch ein Leerzeichen getrennt die ganzen Zahlen $X_i, Y_i$, was bedeutet, dass sich das $i$-te Haus an der Kreuzung $(X_i, Y_i)$ befindet. Diese $N$ Kreuzungen sind alle paarweise verschieden.

Ausgabe

Gib die folgenden Daten auf der Standardausgabe aus:

• Die $1$. Zeile muss $1$ ganze Zahl enthalten, die das Minimum der benötigten Zeit darstellt.
• Die $2$. Zeile muss, wenn $(x, y)$ die Kreuzung ist, an der gelandet werden sollte, um die benötigte Zeit zu minimieren, die $2$ ganzen Zahlen $x, y$ in dieser Reihenfolge durch ein Leerzeichen getrennt enthalten. Falls es mehrere geeignete Kreuzungen gibt, wähle unter ihnen die am weitesten westlich gelegene (d. h. diejenige mit dem kleinsten Wert für $x$); falls sie dadurch immer noch nicht eindeutig auf $1$ Kreuzung festgelegt ist, wähle unter diesen die am weitesten südlich gelegene (d. h. diejenige mit dem kleinsten Wert für $y$).

Beispiel

Beispiel 1

Eingabe

5 4
3
1 1
3 4
5 3

Ausgabe

10
3 3

Erklärung

Beispielsweise kann die benötigte Zeit durch den folgenden Bewegungsplan minimiert werden:

• Lande an der Kreuzung $(3, 3)$.
• Liefere einen Schokoladenkuchen an das Haus an der Kreuzung $(3, 4)$. Die bisher verstrichene Zeit beträgt $1$.
• Kehre zur Kreuzung $(3, 3)$ zurück. Die bisher verstrichene Zeit beträgt $2$.
• Liefere einen Schokoladenkuchen an das Haus an der Kreuzung $(5, 3)$. Die bisher verstrichene Zeit beträgt $4$.
• Kehre zur Kreuzung $(3, 3)$ zurück. Die bisher verstrichene Zeit beträgt $6$.
• Liefere einen Schokoladenkuchen an das Haus an der Kreuzung $(1, 1)$. Die bisher verstrichene Zeit beträgt $10$.

Beispiel 2

Eingabe

4 6
8
1 3
3 2
4 4
2 5
2 3
3 3
3 4
2 4

Ausgabe

21
2 3

Erklärung

Beachte, dass auch an einer Kreuzung gelandet werden darf, an der sich ein Haus befindet.

Bedingungen

• $1 \le W \le 1000000000 = 10^9$: die Anzahl der in Nord-Süd-Richtung verlaufenden Straßen.
• $1 \le H \le 1000000000 = 10^9$: die Anzahl der in Ost-West-Richtung verlaufenden Straßen.
• $1 \le N \le 100000 = 10^5$: die Anzahl der Häuser.
• $1 \le X_i \le W$: die Nummer der Nord-Süd-Straße für den Standort des $i$-ten Hauses.
• $1 \le Y_i \le H$: die Nummer der Ost-West-Straße für den Standort des $i$-ten Hauses.

Beachte, dass bei diesem Problem der Zahlenbereich der verwendeten ganzen Zahlen möglicherweise nicht in $32$ Bit passt.

Bewertung

• Für Testdaten im Wert von $40\%$ der Gesamtpunktzahl gilt $N \le 1000$.
• Für Testdaten im Wert von $10\%$ der Gesamtpunktzahl gilt $W \le 50, H \le 50, N \le 1000$.