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

Poveste şi cerinţă...

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$.
 
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 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 bloca toate tunelurile.

h2. Date de intrare

Fişierul de intrare $sprei.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $sprei.out$ ...

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$
* 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") ==