Зимняя школа Харьков 2014, День 1 - Евгения Капуна (High)

The secret code

Time limit 1 second
Memory limit 256 MiB

After returning from the trip, Alex was unpleasantly surprised: his porch door had a new combination lock. Alex can not get into his house! Code lock contains N disks, each of which can be in one of M positions. There is only one correct position. Alex thoroughly inspected discs and by fingerprints and scratches determined the probability of each position for each disk. Now Alex has K attempts to guess the correct code: if he fails, his vigilant neighbors will call the police, and Alex will have a hard time persuading cops that he is not a thief, but tried to get home. Help Alex to calculate the maximum probability of getting home, not to the police.

Input data

The first line of input file contains three integers: N, M Рё K.

Next N lines contain M integers each: j-th number of the i-th line (Pij) — the probability of a situation where

i-th disc’s correct position is j. Given that Mj=1 Pij =100..

1 ≤ N ≤ 100

1 ≤ M ≤ 20

1 ≤ K ≤ 100

0 ≤ Pij ≤ 100

Output data

Print a single number — Alex’s chances to guess the correct code in time. Output result should have an absolute percentage error not grater than 10 7.


Input example #1
2 2 1
50 50
10 90
Output example #1
Author Евгений Капун
Source Зимняя школа по программированию 2014, Харьков