Fişierul intrare/ieşire:	banana.in, banana.out	Sursă	ONI 2002
Autor	Mihai Patrascu, Roxana Tamplaru	Adăugată de
Timp execuţie pe test	0.025 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	3/5

Banana

Se considera o padure tropicala, reprezentata sub forma unui caroiaj dreptunghiular. Celula din coltul stanga sus al caroiajului are coordonatele (1, 1), iar coordonatele celorlalte celule sunt determinate de linia si coloana pe care se afla. In anumite celule ale caroiajului sunt plasati bananieri; o celula contine cel mult un bananier. Mai multi bananieri care se invecineaza pe orizontala sau verticala formeaza o zona de bananieri. Intr-o astfel de zona, CEKILI se deplaseaza usor, cu agilitatea-i cunoscuta, de la un bananier la altul.

Maimuta CEKILI este lacoma si nu ii ajung bananele dintr-o singura zona. Tarzan vrea sa-si ajute prietena. Pentru aceasta, el ar putea conecta exact K zone de bananieri innodand mai multe liane si astfel CEKILI s-ar putea deplasa de la o zona la alta utilizand lianele. Evident, Tarzan trebuie sa aleaga zonele astfel incat numarul total de bananieri din cele K zone sa fie maxim.

Cerinta

Determinati numarul maxim de bananieri care se poate obtine prin conectarea a exact K zone.

Date de intrare

Fisierul de intrare banana.in contine:

Nr K
x₁ y₁
x₂ y₂
...
x_Nr y_Nr

Nr - numarul de bananieri
K - numarul de zone ce pot fi conectate
x_i - linia pe care se afla bananierul i
y_i - coloana pe care se afla bananierul i

Date de iesire

Fisierul de iesire banana.out va contine pe prima linie numarul maxim de bananieri care se poate obtine prin conectarea zonelor.

Restrictii

1 ≤ Nr ≤ 16 000
1 ≤ x_i, y_i ≤ 10 000, i ∈ {1,2,...,Nr}
in testele utilizate K nu va depasi numarul de zone
doua pozitii se invecineaza pe orizontala daca sunt pe aceeasi linie si pe coloane consecutive, respectiv pe verticala daca sunt pe aceeasi coloana si pe linii consecutive