soldati

Cei $S$ soldați ai unei unități militare au un moment de relaxare și sunt răspândiți pe platou în poziții cunoscute. Evident, ei nu stau aliniați, în poziție de drepți. Platoul poate fi reprezentat printr-un tablou bidimensional cu $n$ linii (numerotate de la $1$ la $n$) și $m$ coloane (numerotate de la $1$ la $m$), o poziție în tablou fiind identificată prin indicele liniei și respectiv al coloanei. Când se anunță sosirea comandantului unității militare, cei $S$ soldați trebuie să se alinieze. Alinierea presupune aşezarea celor $S$ soldaţii pe o aceeași linie $L$, pe coloane consecutive. Ca să nu se creeze haos, fiecare dintre ei se va deplasa numai pe orizontală și verticală. Dacă soldatul $i$ ($1 \leq i \leq S$) se află iniţial în poziţia $(L_i, C_i)$ iar la aliniere ajunge în poziţia $(Lin, Col)$, distanţa pe care el o parcurge va fi $|L_i - Lin| + |C_i - Col|$.

Cerință

Scrieţi un program care să rezolve următoarele două cerințe:

1. determină o linie $Lin$, astfel încât pentru alinierea soldaților pe pozițiile $1, 2, \dots , S$ de pe linia $Lin$, suma distanţelor parcurse de aceştia să fie minimă;
2. determină o linie $Lin$ și o coloană $Col$, astfel încât pentru alinierea soldaților pe linia $Lin$ pe coloanele $Col, Col + 1, \dots, Col + S - 1$, suma distanţelor parcurse de aceştia să fie minimă.

Date de intrare

Fişierul de intrare soldati.in conține pe prima linie 4 valori naturale $C$, $n$, $m$, $S$, separate prin câte un spațiu, reprezentând cerința care trebuie să fie rezolvată, numărul de linii, numărul de coloane, respectiv numărul de soldați. Următoarele $S$ linii conțin pozițiile celor $S$ soldați, câte un soldat pe o linie, pozițiile fiind descrise prin două numere naturale $L$, $C$ separate printr-un spațiu, reprezentând linia, respectiv coloana.

Date de ieșire

Fişierul de ieşire soldati.out va conține pe prima linie un număr natural $D_{min}$ reprezentând distanța totală minimă parcursă pentru ca soldații să se alinieze conform cerinței $C$ din fișierul de intrare. Dacă $C = 1$ pe cea de a doua linie va fi scris un număr natural $Lin$ reprezentând linia pe care se face alinierea. Dacă $C = 2$, pe cea de-a doua linie se vor scrie două numere naturale separate prin spaţiu $Lin$, $Col$, reprezentând linia pe care se va face alinierea, respectiv coloana de la care soldații încep să se alinieze. În cazul în care există mai multe linii pe care soldații se pot alinia parcurgând distanţă totală minimă, se va afișa cea mai mică dintre ele. Pentru $C = 2$, în cazul în care există mai multe coloane $Col$ începând cu care soldații se pot alinia pe linia $Lin$ parcurgând distanţă totală minimă, se va afișa cea mai mică dintre ele.

Restricții și precizări

• $2 \leq n, m \leq 10^6$
• $1 \leq S \leq \min(m, 10^5)$
• Pozițiile inițiale ale soldaților sunt distincte.

Exemplul 1

soldati.in

1 16 17 11
2 3
6 6
6 8
6 9
6 10
6 11
9 6
11 9
13 8
13 6
15 9

soldati.out

54
6

Explicație

Mai jos este reprezentat platoul și modul în care soldații se rearanjează

Exemplul 2

soldati.in

2 16 17 11
2 3
6 6
6 8
6 9
6 10
6 11
9 6
11 9
13 8
13 6
15 9

soldati.out

46
6 3

Explicație

• $2 \ 3 \rightarrow 6 \ 3$
• $4$ pași pe coloana $3$
• $6 \ 6 \rightarrow 6 \ 4$
• $2$ pași pe linia $6$
• $6 \ 8 \rightarrow 6 \ 7$
• $1$ pas pe linia $6$
• $6 \ 9 \rightarrow 6 \ 9$
• $0$ pași (stă pe loc)
• $6 \ 10 \rightarrow 6 \ 12$
• $2$ pași pe linia $6$
• $6 \ 11 \rightarrow 6 \ 13$
• $2$ pași pe linia $6$
• $9 \ 6 \rightarrow 6 \ 5$
• $3$ pași pe coloana $6$ și $1$ pas pe linia $6$
• $11 \ 9 \rightarrow 6 \ 10$
• $5$ pași pe coloana $9$ și $1$ pas pe linia $6$
• $13 \ 8 \rightarrow 6 \ 8$
• $7$ pași pe coloana $8$
• $13 \ 6 \rightarrow 6 \ 6$
• $7$ pași pe coloana $6$
• $15 \ 9 \rightarrow 6 \ 11$
• $9$ pași pe coloana $9$ și $2$ pași pe linia $6$