Lýsing á verkefni

Í lok síðasta árs gleymdi jólasveinninn að gefa börnunum í JOI-þorpinu jólagjafir. Til að biðjast afsökunar ákvað hann því að færa börnunum súkkulaðikökur. Þar sem afhendingardagurinn er á morgun er kominn tími til að hugsa sér ferðaáætlun.

JOI-þorpinu er skipt upp eins og taflborði með $W$ beinum vegum sem liggja í norður-suður og $H$ beinum vegum sem liggja í austur-vestur. Vegirnir $W$ sem liggja í norður-suður eru númeraðir $1, 2, \dots, W$ í röð að vestan, og vegirnir $H$ sem liggja í austur-vestur eru númeraðir $1, 2, \dots, H$ í röð að sunnan. Gatnamótin þar sem $x$-ti norður-suður vegurinn að vestan og $y$-ti austur-vestur vegurinn að sunnan mætast eru táknuð með $(x, y)$. Í JOI-þorpinu eru $N$ hús og hvert þeirra stendur á einhverjum gatnamótum. Jólasveinninn getur aðeins ferðast eftir vegunum. Tíminn sem það tekur að fara á milli aðliggjandi gatnamóta er $1$.

Þar sem börn búa í öllum húsum í JOI-þorpinu verður jólasveinninn að heimsækja öll húsin í JOI-þorpinu og færa hverju húsi $1$ súkkulaðiköku. Þar sem nokkuð hættulegt er að fljúga um loftin blá með hreindýrunum haldandi á dýrmætum súkkulaðikökum ákváðu jólasveinninn og hreindýrin að lenda á einhverjum gatnamótum í JOI-þorpinu, og jólasveinninn mun ganga þaðan til að bera út súkkulaðikökurnar. Jólasveinninn gengur aldrei með $2$ eða fleiri súkkulaðikökur í einu. Það er að segja, í hvert sinn sem jólasveinninn hefur afhent súkkulaðiköku í $1$ hús snýr hann aftur á gatnamótin þar sem hann lenti.

Jólasveinninn ákvað að velja ferðaáætlun sem lágmarkar heildartímann sem það tekur frá því að hann lendir í JOI-þorpinu þar til hann hefur afhent súkkulaðikökur í öll húsin. Athugið að tíminn sem það tekur að snúa aftur á lendingargatnamótin eftir að súkkulaðikakan hefur verið afhent í síðasta húsið er ekki talinn með í heildartímanum. Einnig er ekkert annað en ferðatíminn tekið til greina.

Gefnar eru upplýsingar um staðsetningar húsanna; skrifið forrit sem finnur lággildi heildartímans frá lendingu í JOI-þorpinu þar til súkkulaðikökur hafa verið afhentar í öll húsin þegar jólasveinninn velur lendingargatnamótin á besta hátt, sem og staðsetningu gatnamótanna þar sem hann ætti að lenda til að lágmarka tímann.

Inntak

Lesið eftirfarandi inntak úr staðalinntaki:

• Í $1$. línu eru heiltölurnar $W, H$ aðskildar með bili, sem tákna fjölda vega í hvorri átt.
• Í $2$. línu er heiltala $N$, sem táknar fjölda húsa.
• Næstu $N$ línur innihalda upplýsingar um staðsetningar húsanna. Lína $(i + 2)$ ($1 \le i \le N$) inniheldur heiltölurnar $X_i, Y_i$ aðskildar með bili, sem tákna að $i$-ta húsið standi á gatnamótunum $(X_i, Y_i)$. Þessi $N$ gatnamót eru öll ólík.

Úttak

Skrifið eftirfarandi gögn í staðalúttak:

• Í $1$. línu skal vera $1$ heiltala sem táknar lággildi tímans sem fer í verkið.
• Í $2$. línu, þegar gatnamótin sem lenda skal á til að lágmarka tímann eru $(x, y)$, skulu vera $2$ heiltölur $x, y$ í þessari röð aðskildar með bili. Ef fleiri en ein gatnamót koma til greina skal velja þau sem eru vestust (þ.e. með minnsta gildið á $x$); ef það ákvarðar samt ekki $1$ gatnamót skal velja þau úr þeim hópi sem eru syðst (þ.e. með minnsta gildið á $y$).

Dæmi

Dæmi 1

Inntak

5 4
3
1 1
3 4
5 3

Úttak

10
3 3

Útskýring

Til dæmis má lágmarka tímann með eftirfarandi ferðaáætlun:

• Lent á gatnamótum $(3, 3)$.
• Súkkulaðikaka afhent í húsið á gatnamótum $(3, 4)$. Liðinn tími hingað til er $1$.
• Farið aftur á gatnamót $(3, 3)$. Liðinn tími hingað til er $2$.
• Súkkulaðikaka afhent í húsið á gatnamótum $(5, 3)$. Liðinn tími hingað til er $4$.
• Farið aftur á gatnamót $(3, 3)$. Liðinn tími hingað til er $6$.
• Súkkulaðikaka afhent í húsið á gatnamótum $(1, 1)$. Liðinn tími hingað til er $10$.

Dæmi 2

Inntak

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

Úttak

21
2 3

Útskýring

Athugið að einnig má lenda á gatnamótum þar sem hús stendur.

Takmarkanir

• $1 \le W \le 1000000000 = 10^9$: fjöldi vega sem liggja í norður-suður.
• $1 \le H \le 1000000000 = 10^9$: fjöldi vega sem liggja í austur-vestur.
• $1 \le N \le 100000 = 10^5$: fjöldi húsa.
• $1 \le X_i \le W$: númer norður-suður vegarins þar sem $i$-ta húsið stendur.
• $1 \le Y_i \le H$: númer austur-vestur vegarins þar sem $i$-ta húsið stendur.

Athugið að í þessu verkefni geta heiltölurnar sem unnið er með farið út fyrir $32$ bita svið.

Stigagjöf

• Fyrir prófunargögn sem gilda $40\%$ af heildarstigum gildir $N \le 1000$.
• Fyrir prófunargögn sem gilda $10\%$ af heildarstigum gildir $W \le 50, H \le 50, N \le 1000$.