D. Футболки
ограничение по времени на тест
5 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Вы проходите стажировку в Codeforces с командой из n инженеров, пронумерованных от 1 до n, и хотите подарить каждому из них по сувениру — футболке из Вашей страны (футболки принимаются в Codeforces «на ура!»). К сожалению, вы не знаете, какой размер футболки подойдет каждому инженеру. Всего существует m различных размеров, пронумерованных от 1 до m, и каждому инженеру придется впору футболка ровно одного размера.

Вам неизвестны точные размеры футболок, подходящих инженерам, поэтому вы решили узнать их у Вашего друга Геральда. К сожалению, он тоже не смог выяснить точные размеры, зато для каждого инженера i и для всех размеров j раздобыл вероятность того, что инженеру i подойдет футболка размера j.

Вы решили подарить каждому инженеру по одной футболке, и поэтому собираетесь привезти с собой ровно n футболок. Конечно же, эти n футболок могут быть любых размеров (можно даже привести несколько футболок одного размера!). При выборе футболок-сувениров Вы не знаете точный размер каждого инженера, так что Вам придется выбирать футболки, исходя исключительно из вероятностей, которые предоставил Ваш друг Геральд.

Ваша задача — максимизировать матожидание количества инженеров, которые получат футболки своего размера.

Более формально процесс получения футболок можно описать следующим образом. Когда Вы наконец-то приедете в офис Codeforces, Вы спросите у каждого инженера точный размер его футболки. Затем, если у Вас все еще будет футболка нужного размера, Вы подарите такую футболку данному инженеру, в противном случае не подарите данному инженеру ничего. Вы будете спрашивать размеры у инженеров по порядку, начиная с инженера номер 1, за ним последует инженер номер 2, и так далее до инженера номер n.

Входные данные

В первой строке содержатся два целых числа n и m (1 ≤ n ≤ 3000, 1 ≤ m ≤ 300), записанных через пробел — количество инженеров и количество размеров футболок соответственно.

Затем следует n строк, в каждой строке содержится m целых чисел через пробел. Число номер j в строке номер i обозначает вероятность того, что инженеру номер i будет впору футболка с размером номер j. Каждая вероятность представлена целым числом от 0 до 1000, включительно. Для того, чтобы вычислить, собственно, вероятность, следует разделить соответствующее число на 1000.

Гарантируется, что для любого инженера сумма вероятностей для всех m футболок равняется единице.

Выходные данные

Выведите единственное вещественное число, обозначающее максимально возможное математическое ожидание количества инженеров, которые получат по футболке своего размера.

Допустимая мера абсолютной или относительной погрешности составляет 10 - 9.

Примеры
Входные данные
2 2
500 500
500 500
Выходные данные
1.500000000000
Входные данные
3 3
1000 0 0
1000 0 0
0 1000 0
Выходные данные
3.000000000000
Входные данные
1 4
100 200 300 400
Выходные данные
0.400000000000
Примечание

В первом примере нужно привезти по одной футболке каждого размера. Вероятности того, что либо обоим инженерам будут впору футболки размера номер 1, либо им обоим будут впору футболки с размером номер 2, равна 0.5. Вероятность того, что одному инженеру будет впору футболка размера номер 1, а другому — футболка размера номер 2, также равна 0.5. В первом случае футболку получает только один инженер. В последнем случае по футболке получают два инженера. Следовательно, матожидание количества инженеров, которые получат по футболке, равняется 1.5. Это максимально возможное матожидание количества инженеров для всех комплектов футболок.

Во втором примере нужно привезти две футболки размера номер 1 и одну футболку размера номер 2. Таким образом, каждый инженер несомненно получит по футболке своего размера.

В третьем примере нужно привезти одну футболку размера номер 4.