==Include(page="template/taskheader" task_id="banana")==

==Include(page="template/raw")==
 

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.

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

h2. Date de intrare

h2. Date de Intrare

Fisierul de intrare $banana.in$ contine:

table(example). | Nr K

 
table(example). | banana.in | semnificatie |
| Nr K

x{~1~} y{~1~}
x{~2~} y{~2~}
...

  x{~i~} - linia pe care se afla bananierul i
  y{~i~} - coloana pe care se afla bananierul i |

h2. Date de iesire

h2. Date de Iesire

Fisierul de iesire $banana.out$ va contine pe prima linie numarul maxim de bananieri care se poate obtine prin conectarea zonelor.
h2. Restrictii
* $1 ≤ Nr ≤ 16 000$

* $1 ≤ x{~i~}, y{~i~} ≤ 10 000, i ∈ {1,2,...,Nr}$

* $1 ≤ x{~i~}, y{~i~} ≤ 10 000, i  _FIXME: APARTINE_ {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

| 9 |
==Include(page="template/taskfooter" task_id="banana")==

869