Sprei

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.

Paul are o problema mare cu gandacii in casa, el trebuie sa omoare 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$.

Un gandac poate fi reprezentat prin ADN-ul sau - un vector de numere naturale de lungime M cu valori de la $0$ la $B - 1$.
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$).

O colonie de gandaci poate fi 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 (exista o unica pozitie in vectorul lor de pozitie si este de exact 1), acestia isi construiesc un wormhole intre cele doua colonii.

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$.

Paul stie pozitiile celor N colonii, si doreste sa blocheze toate wormholurile dintre colonii.
Pentru asta, el poate achizitiona spreiuri speciale, cu un sprei putand dezactiva toate wormholurile plecand dintr-o colonie.

h2. Cerinta

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

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

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 ADN-ul fiecarui gandac.

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

h2. Date de ieşire

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

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

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

* Se garanteza ca toti gandacii au ADN-uri *distincte doua cate doua*.
* Pentru teste in valoare de $30$ de puncte $1 ≤ N ≤ 20$

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

h2. Exemplu

Alegem doua tuburi de sprei:

* 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$

* Unul bazat pe pozitia $1 1 1$
* Unul bazat pe pozitia $1 1 2$

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