==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{~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 |

| $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$ ||
 
 
banana.in ]Semnificatie
Nr K Nr - numarul de bananieri
 
x[1] y[1 K - numarul de zone ce pot fi conectate
 
]x[2] y[2 x[i] - linia pe care se afla bananierul i
 
]... y[i] - coloana pe care se afla bananierul i
 
x[Nr] y[Nr

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.

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

Ÿ 1 -L- Nr -L- 16 000
 
Ÿ 1 -L- xi, yi -L- 10 000, "iI{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.

h2. Exemplu

table(example). |_. banana.in |_. banana.out |
| 10 3
7 10
1 1
101 1
2 2
102 1
7 11
200 202
2 1
3 2
103 1
| 9 |

 
|banana.in |banana.out |
 
|10 3 |9 |
| | |
|7 10 | |
| | |
|1 1 | |
| | |
|101 1 | |
| | |
|2 2 | |
| | |
|102 1 | |
| | |
|7 11 | |
| | |
|200 202 | |
| | |
|2 1 | |
| | |
|3 2 | |
| | |
|103 1 | |
| | |
| | |
 
 

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

869