gradina

Bunicul are o grădină mare, împărțită în $L$ rânduri și $C$ coloane egale. În această grădină, el a plantat $M$ flori din specii rare, fiecare floare ocupând o singură celulă a grădinii. Restul spațiilor din grădină sunt ocupate de gazon.

Pentru că se apropie o sărbătoare, bunicul vrea să replanteze florile astfel încât ele să formeze o zonă dreptunghiulară compactă (un dreptunghi plin, fără spații libere între flori). Acest dreptunghi poate fi plasat oriunde în grădină și poate avea orice dimensiuni $h$ (rânduri) și $w$ (coloane), cu singura condiție ca numărul total de celule ocupate să fie egal cu numărul de flori, adică $h \cdot w = M$. Deoarece bunicul depune efort la fiecare floare mutată, el vrea să știe care este numărul minim de flori pe care trebuie să le scoată din poziția lor actuală și să le replanteze în alt loc pentru a obține forma dorită.

Cerință

Cunoscând dimensiunile grădinii $L$ și $C$, numărul de flori $M$ și coordonatele (rând, coloană) unde se află fiecare floare în prezent, scrieți un program care determină:

1. Pentru $V=1$, numărul rândului sau rândurilor care conțin cele mai multe flori în acest moment.
2. Pentru $V=2$, numărul minim de flori ce trebuie mutate pentru ca toate cele $M$ flori să fie grupate într-o zonă dreptunghiulară compactă.

Date de intrare

Fișierul de intrare gradina.in conține:

• Pe prima linie numărul natural $V$ (valoarea $1$ sau $2$, reprezentând cerința).
• Pe a doua linie numerele naturale $L$ și $C$, reprezentând numărul de rânduri și de coloane.
• Pe a treia linie numărul natural $M$, reprezentând numărul de flori.
• Pe următoarele $M$ linii, câte o pereche de valori $x_i$ și $y_i$, $1 \leq i \leq M$, reprezentând linia și coloana unde se află inițial fiecare floare. Valorile sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire gradina.out conține:

• Dacă $V = 1$, se vor afișa în ordine crescătoare indicii rândurilor care conțin numărul maxim de flori.
• Dacă $V = 2$, se va afișa numărul minim de flori pe care bunicul trebuie să le replanteze. Dacă acestea nu pot fi așezate într-un dreptunghi compact, se va afișa valoarea $-1$.

Restricții și precizări

• $1 \leq L, C \leq 500$;
• $1 \leq M \leq L \cdot C$;
• $1 \leq x_i \leq L$, $1 \leq y_i \leq C$;
• Pentru cerința $2$, se iau în considerare toate perechile de numere naturale $(h, w)$ astfel încât $h \cdot w = M$, $h \leq L$ și $w \leq C$;

Exemplul 1

gradina.in

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

gradina.out

4

Explicație

$V = 1$, deci se rezolvă doar cerința $1$. Pe linia $1$ se află $2$ flori. Pe linia 2 se află 1 floare. Pe linia $3$ sunt $2$ flori. Pe linia $4$ sunt $3$ flori. Așadar, există o singură linie pe care sunt un număr maxim de flori: linia $4$.

Exemplul 2

gradina.in

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

gradina.out

3

Explicație

$V = 2$, deci se rezolvă doar cerința $2$. Pentru a obține o zonă compactă de formă dreptunghiulară trebuie mutate minimum $3$ flori. O variantă posibilă este: floarea de la poziția $(1,2)$ se mută la poziția $(3,3)$, floarea de la poziția $(1,5)$ se mută la poziția $(3,4)$ și floarea de la poziția $(2,1)$ se mută la poziția $(4,2)$. Se obține o zonă compactă de formă dreptunghiulară, având colțul din stânga sus la poziția $(3,2)$ și colțul din dreapta jos la poziția $(4,5)$.