serbare

Majoritatea copiilor sunt sociabili şi relaţionează uşor cu cei de vârsta lor dar sunt şi copii mai timizi sau mai puţin atraşi de activităţile de grup. În urma studierii comportamentului unui eşantion de $n$ copii, s-a stabilit, pentru fiecare doi copii dacă relaţionează sau nu. Pentru serbarea de sfârşit de an, s-a propus realizarea unei scenete şi este necesară selectarea unei grupe cât mai numeroase de micuţi dar fără a depăşi $k$, numărul maxim de personaje. Rolurile presupun interacţiunea fiecărui copil selectat cu toţi ceilalţi mici actori care joacă în scenetă.

Cerinţă

Cunoscand $n$ – dimensiunea eşantionului studiat, capacitatea fiecarui copil de a relaţiona cu ceilalţi şi $k$ - numărul maxim de personaje din scenetă, să se determine cel mai mare număr de copii care pot fi implicaţi în serbare, ştiind ca fiecare dintre aceştia trebuie să relaţioneze cu toţi ceilalţi copii din scenetă.

Date de intrare

Fişierul de intrare serbare.in conţine $n+1$ linii şi are structura:

• $n \ k$, unde $n$ = dimensiunea eşantionului; $k$ = numărul maxim de personaje
• $a_{(1, 1)} \ a_{(1, 2)} \dots a_{(1, n)}$, unde $a_{(i, j)} = 1$, dacă copilul $i$ relaţionează cu copilul $j$ sau $a_{(i, j)} = 0$, altfel
• $a_{(2, 1)} \ a_{(2, 2)} \dots a_{(2, n)}$
• $\dots$
• $a_{(n, 1)} \ a_{(n, 2)} \dots a_{(n, n)}$

Date de ieşire

Fişierul de ieşire serbare.out conţine o singurã linie pe care se va scrie numărul maxim de copii care vor selectaţi pentru a juca în scenetă.

Restricţii şi precizări:

• $2 \leq n \leq 100$
• $2 \leq k \leq 10$
• Se considera ca un copil NU este relaţionează cu el insuşi.

Exemplul 1

serbare.in

3 3
0 1 1
1 0 1
1 1 0

serbare.out

3

Exemplul 2

serbare.in

4 3
0 1 0 1
1 0 1 0
0 1 0 0
1 0 0 0

serbare.out

2