Наборы для ставок
Ваше местное казино (которое находится здесь, в Калифорнии, на приличном расстоянии) решило попробовать новую азартную игру. Игроку предоставляется карточка с таблицей размером N на M. Каждая ячейка i j в таблице соответствует подбрасыванию монеты, где вероятность выпадения орла равна p_ij. Все подбрасывания монет независимы. Игрок должен выбрать N наборов из M записей, при этом в каждом наборе должна быть ровно одна запись из каждого столбца, и каждая запись используется ровно один раз. За каждый набор, в котором все M монет выпадают орлом, игрок выигрывает 1 доллар. Казино проявляет необычайную щедрость и в рамках продвижения этой новой игры раздает по одной карточке каждому посетителю. Поскольку вам нечего терять, вы решили попробовать эту игру. Как вы можете максимизировать свои ожидаемые выигрыши с этой карточки?
Входные данные
Входные данные состоят из нескольких тестов. Каждый тест начинается со строки с двумя целыми числами N и M, 1 ≤ N ≤ 100, 1 ≤ M ≤ 10, разделенными пробелом. Далее следуют N строк с M числами, разделенными пробелами, обозначающими значения p_ij в таблице. Входные данные завершаются строкой с N = M = 0, которую не следует обрабатывать.
Выходные данные
Для каждого теста выведите одну строку с максимальными ожидаемыми выигрышами из данной таблицы, с точностью до 4 десятичных знаков.