Sprei

Paul are o problema mare cu gandacii in casa, el trebuie sa nimiceasca cat mai repede cele $N$ colonii gandaci ce i-au infestat casa.
Fiind o persoana abstracta, acesta traieste intr-un cub $M$ dimensional, in care fiecare pozitie poate fi codificata printr-un vector $A ~1~, A ~2~ ... A ~M~$ cu valori intre $0$ si $B - 1$.

Paul are o problema mare cu gandacii in casa, el trebuie sa omoare cat mai repede toti cei N gandaci ce i-au infestat casa.

O colonie de gandaci este reprezentata prin pozitia sa - un vector de numere naturale de lungime M cu valori de la $0$ la $B - 1$.
Fiind entitati sociale, gandacii incearca sa isi uneasca coloniile. Asftel, daca doua colonii ocupa pozitii adiatente in casa lui Paul (pozitia uneia se obtine adaugand sau scand $1$ din pozitia celeilalte), acestia isi construiesc un tunel intre cele doua colonii.

Un gandac poate fi reprezentat prin ADN-ul sau - un vector de numere naturale de lungime M cu valori de la $1$ la $B$.
Pentru a se adapta mediului, gandacii urmeaza mai multe mutatii, o mutatie luand harta ADN a unui gandac si crescand sau scazand $exact$ o pozitie cu 1 (nu poate creste daca este $B$ si nu poate scadea daca este $1$).

Paul stie pozitiile celor $N$ colonii, si doreste sa blocheze toate tunelurile din ele.
Pentru asta, el poate achizitiona spreiuri speciale.
Exista $N$ tipuri de sprei, sprei-ul de tip $i$ distrugand toate tunelurile avand unul dintre cele doua capete colonia $i$.

Paul stie ADN-ul tuturor gandacilor si stie ca poate creea pentru un anumit ADN $X$ un sprai care omoara toti gandacii cu ADN-ul $X$ sau o mutatie directa de-al lui $X$.

h2. Cerinta

Paul vrea sa stie care este numarul minim de sprai-uri necesare pentru a bloca toate tunelurile.

Paul vrea sa stie care este numarul minim de sprai-uri necesare pentru a omori toti gandacii.

h2. Date de intrare
Pe prima linie a fisierului $sprei.in$ se dau $N, M, B$.

Pe urmatoarele $N$ linii urmeaza cate $M$ numere intre $1$ si $B$ care reprezinta pozitia fiecarei colonii.

Pe urmatoarele $N$ linii urmeaza cate $M$ numere intre $1$ si $B$ care reprezinta ADN-ul fiecarui gandac.

h2. Date de ieşire

Pe prima linie a fisierului $sprei.out$ afisati numarul minim de spreiuri necesare pentru a bloca toate tunelurile.

Pe prima linie a fisierului $sprei.out$ afisati numarul minim de spreiuri necesare pentru a omora toti gandacii.

h2. Restricţii
* $1 ≤ N ≤ 10.000$
* $1 ≤ B ≤ 10^9^$
* $1 ≤ M ≤ 100$

* Se garanteza ca toate coloniile au pozitii *distincte doua cate doua*.
* Pentru teste in valoare de $30$ de puncte $1 ≤ N ≤ 10$

* *NU* se garanteza ca toti gandacii au ADN diferit
* Din motive evolutionare, pentru $70%$ din teste se garanteaza ca oricum am alege un gandac cu ADN-ul $X$ exista cel putin un alt gandac cu ADN-ul mutatie directa de-al lui $X$.

h2. Exemplu
table(example). |_. sprei.in |_. sprei.out |

| 5 3 4

| 5 3 3

1 1 1
1 1 2
1 1 3

h3. Explicaţie

Cumparam doua tuburi de sprei:

Alegem doua tuburi de sprei:

* Un sprei de tipul $1$
* Un sprei de tipul $3$

* Unul bazat pe ADN-ul $1 1 1$, care poate omora gandacii $1, 2 si 4$
* Unul bazat pe ADN-ul $1 1 3$, care poate omora gandacii $2, 3 si 5$

== include(page="template/taskfooter" task_id="sprei") ==