bal

Deoarece K.L 2.0 s-a săturat de probleme de numărare, el s-a hotărât să organizeze un bal. La bal participă $N$ fete şi $N$ băieţi. Imediat cum au auzit de acest bal, fetele au început să îşi facă planuri, astfel că şi-au notat preferinţele lor pentru partenerii de dans, fiecare fată scriind cât de fericită ar fi dacă ar dansa cu un anumit partener. Din nefericire, fetele şi-au pierdut notiţele şi nu mai ştiu care cu ce băiat voiau să meargă la dans. Totuşi, înainte de a le rătăci, fetele le-au transmis notiţele participanţilor la LOT. Prin urmare, pentru fiecare băiat, se cunoaşte probabilitatea ca o fată să fie fericită dacă dansează cu el. În plus, oricare băiat care dansează nu vrea să îşi dezamăgească partenera, iar din această cauză nu poate dansa cu mai mult de $K$ fete fără a-şi diminua performanţele.

Cerință

Voi trebuie să determinaţi probabilitatea maximă care se poate obţine astfel încât cele $N$ fete să fie fericite, iar apoi K.L 2.0 vă va recompensa cu $100$ de puncte.

Date de intrare

Fişierul de intrare bal.in conţine pe prima linie numerele naturale nenule $N$ şi $K$, separate printr-un spaţiu, reprezentând numărul de fete şi de băieţi, respectiv numărul maxim de partenere cu care poate dansa un băiat. Următoarele $N$ linii conţin câte $N$ valori naturale. Linia $i+1$ conţine, separate prin câte un spaţiu, valorile $P_{i, 1}, P_{i, 2}, \dots, P_{i, N}$ care semnifică probabilităţile (exprimate în procente) ca băiatul $i$ să le facă fericite pe fiecare din cele $N$ fete dacă dansează cu ele.

Date de ieșire

Fişierul de ieşire bal.out va conţine pe prima linie un singur număr care reprezintă probabilitatea maximă (exprimată în procente) care se poate obţine ca cele $N$ fete să fie fericite.

Restricții și precizări

• $1 \leq K \leq N \leq 250$
• $0 \leq P_{i, j} \leq 100$
• Se consideră corectă o soluţie în care probabilitatea maximă diferă cu cel mult $0.01$ faţă de rezultatul corect.
• Pentru $10\%$ din teste, $K = N$
• Pentru alte $10\%$ din teste $N \leq 10$
• K.L 2.0 este un roboţel mic, nevinovat şi mai ales singur cuc. Din acest motiv el vă recomandă să folosiţi tipul de date double.

Exemplul 1

bal.in

2 2
40 60
25 0

bal.out

24.00

Explicație

Primul băiat va dansa cu ambele fete, rezultând o probabilitate de $40\%$ înmulţită cu $60\%$. Dacă ar fi dansat al doilea băiat cu prima fată, s-ar fi obţinut o probabilitate mai mică, şi anume de $15\%$.

Exemplul 2

bal.in

3 1
80 25 11
66 42 11
8 11 100

bal.out

33.60

Explicație

Soluţia se obţine dacă dansează primul băiat cu prima fată, al doilea băiat cu a doua fată şi al treilea băiat cu a treia fată: $80\%$ înmulţit cu $42\%$ înmulţit cu $100\%$.