Problembeskrivelse

På slutten av fjoråret glemte julenissen å gi julegaver til barna i landsbyen JOI. Som en unnskyldning bestemte han seg derfor for å levere sjokoladekaker til barna. Siden leveringsdagen er allerede i morgen, må han snart legge en reiseplan.

Landsbyen JOI er delt inn som et rutenett av $W$ rette veier som går i nord-sør-retning og $H$ rette veier som går i øst-vest-retning. De $W$ nord-sør-veiene er nummerert $1, 2, \dots, W$ i rekkefølge fra vest, og de $H$ øst-vest-veiene er nummerert $1, 2, \dots, H$ i rekkefølge fra sør. Krysset der den $x$-te nord-sør-veien fra vest og den $y$-te øst-vest-veien fra sør møtes, betegnes med $(x, y)$. Det er $N$ hus i landsbyen JOI, og hvert av dem ligger i et av kryssene. Julenissen kan kun bevege seg langs veiene. Tiden det tar å bevege seg mellom to nabokryss er $1$.

Siden det bor barn i alle husene i landsbyen JOI, må julenissen besøke hvert eneste hus i landsbyen JOI og levere $1$ sjokoladekake til hvert hus. Fordi det er litt farlig å fly rundt i luften med reinsdyrene mens man holder på de verdifulle sjokoladekakene, bestemte julenissen og reinsdyrene seg for å lande i et av kryssene i landsbyen JOI, og så går julenissen derfra til fots for å levere sjokoladekakene. Julenissen går aldri rundt med $2$ eller flere sjokoladekaker samtidig. Det vil si at hver gang julenissen har levert en sjokoladekake til $1$ hus, går han tilbake til krysset der han landet.

Julenissen har bestemt seg for å velge en reiseplan som minimerer den totale tiden det tar fra han lander i landsbyen JOI til han har levert sjokoladekaker til alle husene. Merk at tiden det tar å gå tilbake til landingskrysset etter at han har levert sjokoladekake til det siste huset, ikke regnes med i tidsbruken. Dessuten tas det ikke hensyn til noe annet enn tiden som går med til selve forflytningen.

Gitt informasjonen om husenes posisjoner, skriv et program som finner den minste mulige tidsbruken fra julenissen lander i landsbyen JOI til han har levert sjokoladekaker til alle husene når han velger landingskrysset optimalt, samt posisjonen til krysset der han bør lande for å minimere tidsbruken.

Inndata

Les følgende inndata fra standard inndata:

• Den $1$. linjen inneholder heltallene $W, H$ atskilt med mellomrom, som angir antallet veier i hver retning.
• Den $2$. linjen inneholder et heltall $N$, som angir antallet hus.
• De neste $N$ linjene inneholder informasjon om husenes posisjoner. Den $(i + 2)$-te linjen ($1 \le i \le N$) inneholder heltallene $X_i, Y_i$ atskilt med mellomrom, som angir at det $i$-te huset ligger i krysset $(X_i, Y_i)$. Disse $N$ kryssene er alle forskjellige.

Utdata

Skriv ut følgende data til standard utdata:

• Den $1$. linjen skal inneholde $1$ heltall som representerer den minimale tidsbruken.
• Den $2$. linjen skal, når krysset der julenissen bør lande for å minimere tidsbruken er $(x, y)$, inneholde de $2$ heltallene $x, y$ i denne rekkefølgen atskilt med mellomrom. Hvis det finnes flere passende kryss, velg det som ligger lengst mot vest (det vil si det med minst verdi av $x$) blant dem; hvis det fortsatt ikke entydig bestemmer $1$ kryss, velg det blant disse som ligger lengst mot sør (det vil si det med minst verdi av $y$).

Eksempel

Eksempel 1

Inndata

5 4
3
1 1
3 4
5 3

Utdata

10
3 3

Forklaring

For eksempel kan tidsbruken minimeres ved hjelp av følgende reiseplan:

• Land i krysset $(3, 3)$.
• Lever en sjokoladekake til huset som ligger i krysset $(3, 4)$. Tiden som har gått så langt er $1$.
• Gå tilbake til krysset $(3, 3)$. Tiden som har gått så langt er $2$.
• Lever en sjokoladekake til huset som ligger i krysset $(5, 3)$. Tiden som har gått så langt er $4$.
• Gå tilbake til krysset $(3, 3)$. Tiden som har gått så langt er $6$.
• Lever en sjokoladekake til huset som ligger i krysset $(1, 1)$. Tiden som har gått så langt er $10$.

Eksempel 2

Inndata

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

Utdata

21
2 3

Forklaring

Merk at det også er tillatt å lande i et kryss der det ligger et hus.

Begrensninger

• $1 \le W \le 1000000000 = 10^9$: antallet veier som går i nord-sør-retning.
• $1 \le H \le 1000000000 = 10^9$: antallet veier som går i øst-vest-retning.
• $1 \le N \le 100000 = 10^5$: antallet hus.
• $1 \le X_i \le W$: nummeret på nord-sør-veien for posisjonen til det $i$-te huset.
• $1 \le Y_i \le H$: nummeret på øst-vest-veien for posisjonen til det $i$-te huset.

Merk at i denne oppgaven kan verdiområdet for heltallene som behandles overstige $32$ biter.

Poengberegning

• For testdata verdt $40\%$ av total poengsum gjelder $N \le 1000$.
• For testdata verdt $10\%$ av total poengsum gjelder $W \le 50, H \le 50, N \le 1000$.