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

Un gandac poate fi reprezentat prin harta ADN-ul sau - un cuvant de lungime M in baza B.

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.

Paul stie reprezentarile hartilor tuturor gandacilor si stie ca poate creea pentru o anumita harta ADN X un sprai care poate sa omoare toti gandacii cu o harta ADN Y cu proprietatea ca X si Y difera in maxim o pozitie c, si  |X ~c~ - Y ~c~ | <= 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$.

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

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 $0$ si $B-1$ care reprezinta harta ADN a 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 tunelurile.

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

* *NU* se garanteza ca toti gandacii au ADN diferit

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

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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5 3 4
1 1 1
1 1 2
1 1 3
1 2 1
1 2 3
| 2

|
h3. Explicaţie

...

Cumparam doua tuburi de sprei:
 
* Un sprei de tipul $1$
* Un sprei de tipul $3$

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