Есептің шарты

Өткен жылдың соңында Санта-Клаус JOI ауылының балаларына Рождестволық сыйлықтар беруді ұмытып кетті. Сондықтан кешірім ретінде ол балаларға шоколадты торттар жеткізіп беруді ұйғарды. Жеткізіп беретін күн ертең болғандықтан, енді қозғалыс жоспарын ойластыру керек.

JOI ауылы солтүстік-оңтүстік бағытта түзу созылған $W$ жолмен және шығыс-батыс бағытта түзу созылған $H$ жолмен тор көзді тақта пішінінде бөлінген. Солтүстік-оңтүстік бағыттағы $W$ жол батыстан бастап ретімен $1, 2, \dots, W$ сандарымен нөмірленген, ал шығыс-батыс бағыттағы $H$ жол оңтүстіктен бастап ретімен $1, 2, \dots, H$ сандарымен нөмірленген. Батыстан санағанда $x$-ші солтүстік-оңтүстік жол мен оңтүстіктен санағанда $y$-ші шығыс-батыс жол қиылысатын жол қиылысы $(x, y)$ деп белгіленеді. JOI ауылында $N$ үй бар және олардың әрқайсысы қандай да бір жол қиылысында орналасқан. Санта-Клаус тек жолдардың бойымен ғана қозғала алады. Көршілес жол қиылыстарының арасында жүруге кететін уақыт $1$-ге тең.

JOI ауылындағы барлық үйде балалар бар болғандықтан, Санта-Клаус JOI ауылындағы барлық үйді аралап, әрқайсысына $1$ шоколадты торттан жеткізіп шығуы керек. Бағалы шоколадты торттарды ұстап алып, бұғылармен аспанда ұшып жүру біршама қауіпті болғандықтан, Санта-Клаус пен бұғылар JOI ауылындағы жол қиылыстарының біріне қонып, Санта-Клаус сол жерден жаяу жүріп шоколадты торттарды таратуды ұйғарды. Санта-Клаус бір мезгілде $2$ немесе одан көп шоколадты тортты көтеріп жүрмейді. Яғни, Санта-Клаус шоколадты тортты $1$ үйге жеткізген сайын өзі қонған жол қиылысына қайтып оралады.

Санта-Клаус JOI ауылына қонған сәттен бастап барлық үйге шоколадты торттарды жеткізіп болғанға дейін кететін жалпы уақыт ең аз болатындай қозғалыс жоспарын таңдауды ұйғарды. Соңғы үйге шоколадты тортты жеткізгеннен кейін қонған жол қиылысына қайтып оралуға кететін уақыт қажетті уақытқа қосылмайтынына назар аударыңыз. Сондай-ақ қозғалысқа кететін уақыттан басқа ештеңе ескерілмейді.

Үйлердің орналасуы туралы ақпарат берілген кезде, Санта-Клаус қонатын жол қиылысын оңтайлы таңдаған жағдайда JOI ауылына қонғаннан бастап барлық үйге шоколадты торттарды жеткізгенге дейінгі қажетті уақыттың ең кіші мәнін және қажетті уақытты барынша азайту үшін қонуы тиіс жол қиылысының орнын табатын программа жазыңыз.

Кіріс деректер

Стандартты кірістен келесі деректерді оқыңыз:

• $1$-ші жолда әр бағыттағы жолдар санын білдіретін, бос орын арқылы бөлінген $W, H$ бүтін сандары берілген.
• $2$-ші жолда үйлердің санын білдіретін $N$ бүтін саны берілген.
• Келесі $N$ жолда үйлердің орналасуы туралы ақпарат берілген. $(i + 2)$-ші жолда ($1 \le i \le N$) бос орын арқылы бөлінген $X_i, Y_i$ бүтін сандары берілген, олар $i$-ші үйдің $(X_i, Y_i)$ жол қиылысында орналасқанын білдіреді. Бұл $N$ жол қиылысының барлығы әртүрлі.

Шығыс деректер

Стандартты шығысқа келесі деректерді шығарыңыз:

• $1$-ші жолда қажетті уақыттың ең кіші мәнін білдіретін $1$ бүтін сан жазылуы тиіс.
• $2$-ші жолда қажетті уақытты барынша азайту үшін қонуға тиісті жол қиылысы $(x, y)$ болғанда, осы ретпен бос орын арқылы бөлінген $2$ бүтін сан $x, y$ жазылуы тиіс. Егер қолайлы жол қиылыстары бірнешеу болса, олардың ішінен ең батыста орналасқанын (яғни $x$ мәні ең кішісін), ал егер сонда да $1$ қиылыс бірмәнді анықталмаса, олардың ішінен ең оңтүстікте орналасқанын (яғни $y$ мәні ең кішісін) таңдаңыз.

Мысал

Мысал 1

Кіріс деректер

5 4
3
1 1
3 4
5 3

Шығыс деректер

10
3 3

Түсіндірме

Мысалы, келесі қозғалыс жоспары арқылы қажетті уақытты ең аз етуге болады:

• $(3, 3)$ жол қиылысына қону.
• $(3, 4)$ жол қиылысында орналасқан үйге шоколадты торт жеткізу. Осы сәтке дейін өткен уақыт — $1$.
• $(3, 3)$ жол қиылысына қайтып оралу. Осы сәтке дейін өткен уақыт — $2$.
• $(5, 3)$ жол қиылысында орналасқан үйге шоколадты торт жеткізу. Осы сәтке дейін өткен уақыт — $4$.
• $(3, 3)$ жол қиылысына қайтып оралу. Осы сәтке дейін өткен уақыт — $6$.
• $(1, 1)$ жол қиылысында орналасқан үйге шоколадты торт жеткізу. Осы сәтке дейін өткен уақыт — $10$.

Мысал 2

Кіріс деректер

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

Шығыс деректер

21
2 3

Түсіндірме

Үй орналасқан жол қиылысына да қонуға болатынына назар аударыңыз.

Шектеулер

• $1 \le W \le 1000000000 = 10^9$: солтүстік-оңтүстік бағытта созылған жолдар саны.
• $1 \le H \le 1000000000 = 10^9$: шығыс-батыс бағытта созылған жолдар саны.
• $1 \le N \le 100000 = 10^5$: үйлер саны.
• $1 \le X_i \le W$: $i$-ші үйдің орналасқан жерінің солтүстік-оңтүстік бағыттағы жол нөмірі.
• $1 \le Y_i \le H$: $i$-ші үйдің орналасқан жерінің шығыс-батыс бағыттағы жол нөмірі.

Бұл есепте қарастырылатын бүтін сандардың ауқымы $32$ битке сыймауы мүмкін екеніне назар аударыңыз.

Бағалау критерийлері

• Жалпы ұпайдың $40\%$ құрайтын тест деректері үшін $N \le 1000$ орындалады.
• Жалпы ұпайдың $10\%$ құрайтын тест деректері үшін $W \le 50, H \le 50, N \le 1000$ орындалады.