Problembeskrivning

I slutet av förra året glömde jultomten att ge julklappar till barnen i byn JOI. Som en ursäkt bestämde han sig därför för att leverera chokladtårtor till barnen. Eftersom leveransdagen är redan i morgon är det hög tid att tänka ut en resplan.

Byn JOI är indelad i ett rutnät av $W$ raka vägar som går i nord-sydlig riktning och $H$ raka vägar som går i öst-västlig riktning. De $W$ nord-sydliga vägarna är numrerade $1, 2, \dots, W$ i ordning från väster, och de $H$ öst-västliga vägarna är numrerade $1, 2, \dots, H$ i ordning från söder. Korsningen där den $x$:te nord-sydliga vägen från väster och den $y$:te öst-västliga vägen från söder möts betecknas med $(x, y)$. I byn JOI finns det $N$ hus, och vart och ett av dem ligger i någon korsning. Jultomten kan bara förflytta sig längs vägarna. Tiden det tar att förflytta sig mellan två intilliggande korsningar är $1$.

Eftersom det finns barn i alla hus i byn JOI måste jultomten besöka alla hus i byn JOI och lämna $1$ chokladtårta i varje hus. Då det är lite farligt att flyga runt i luften med renarna medan man håller i de dyrbara chokladtårtorna bestämde sig jultomten och renarna för att landa i någon av korsningarna i byn JOI, varifrån jultomten går till fots för att leverera chokladtårtorna. Jultomten bär aldrig med sig $2$ eller fler chokladtårtor samtidigt när han går. Det vill säga, varje gång jultomten har levererat en chokladtårta till $1$ hus återvänder han till korsningen där han landade.

Jultomten har bestämt sig för att välja en resplan som minimerar den totala tiden från det att han landar i byn JOI tills han har levererat chokladtårtor till alla hus. Observera att tiden det tar att återvända till landningskorsningen efter att ha levererat chokladtårtan till det sista huset inte räknas in i den totala tiden. Dessutom tas ingen hänsyn till något annat än själva förflyttningstiden.

Givet informationen om husens placeringar, skriv ett program som beräknar det minsta möjliga värdet på tiden det tar från landningen i byn JOI tills chokladtårtor har levererats till alla hus om jultomten väljer landningskorsning optimalt, samt positionen för den korsning där han bör landa för att minimera denna tid.

Indata

Läs följande indata från standardinmatningen:

• Den $1$:a raden innehåller heltalen $W, H$ separerade med mellanslag, vilka anger antalet vägar i respektive riktning.
• Den $2$:a raden innehåller ett heltal $N$, som anger antalet hus.
• De följande $N$ raderna innehåller information om husens placeringar. Den $(i + 2)$:a raden ($1 \le i \le N$) innehåller heltalen $X_i, Y_i$ separerade med mellanslag, vilket anger att det $i$:te huset ligger i korsningen $(X_i, Y_i)$. Dessa $N$ korsningar är alla olika.

Utdata

Skriv ut följande data till standardutmatningen:

• Den $1$:a raden ska innehålla $1$ heltal som anger den minimala tidsåtgången.
• Den $2$:a raden ska, när den korsning där jultomten bör landa för att minimera tidsåtgången är $(x, y)$, innehålla de $2$ heltalen $x, y$ i denna ordning separerade med ett mellanslag. Om det finns flera lämpliga korsningar, välj den som ligger längst västerut (det vill säga den med minst värde på $x$); om det ändå inte entydigt bestämmer $1$ korsning, välj bland dessa den som ligger längst söderut (det vill säga den med minst värde på $y$).

Exempel

Exempel 1

Indata

5 4
3
1 1
3 4
5 3

Utdata

10
3 3

Förklaring

Till exempel kan tidsåtgången minimeras genom följande resplan:

• Landa i korsningen $(3, 3)$.
• Leverera en chokladtårta till huset som ligger i korsningen $(3, 4)$. Den förflutna tiden hittills är $1$.
• Återvänd till korsningen $(3, 3)$. Den förflutna tiden hittills är $2$.
• Leverera en chokladtårta till huset som ligger i korsningen $(5, 3)$. Den förflutna tiden hittills är $4$.
• Återvänd till korsningen $(3, 3)$. Den förflutna tiden hittills är $6$.
• Leverera en chokladtårta till huset som ligger i korsningen $(1, 1)$. Den förflutna tiden hittills är $10$.

Exempel 2

Indata

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

Utdata

21
2 3

Förklaring

Observera att det är tillåtet att landa i en korsning där det ligger ett hus.

Begränsningar

• $1 \le W \le 1000000000 = 10^9$: antalet vägar som går i nord-sydlig riktning.
• $1 \le H \le 1000000000 = 10^9$: antalet vägar som går i öst-västlig riktning.
• $1 \le N \le 100000 = 10^5$: antalet hus.
• $1 \le X_i \le W$: vägnumret för den nord-sydliga vägen vid det $i$:te husets position.
• $1 \le Y_i \le H$: vägnumret för den öst-västliga vägen vid det $i$:te husets position.

Observera att i detta problem kan storleken på de heltal som hanteras överskrida $32$ bitar.

Poängsättning

• För testfall värda $40\%$ av den totala poängen gäller $N \le 1000$.
• För testfall värda $10\%$ av den totala poängen gäller $W \le 50, H \le 50, N \le 1000$.