Набори для ставок
Ваше місцеве казино (яке розташоване тут, у Каліфорнії, на певній відстані) вирішило запровадити нову гру на ставки. Гравцю надається картка з таблицею, що має 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 десяткових знаків.