당신이 방문한 카지노(강원랜드에서 멀리 떨어진..)는 최근에 새로운 게임을 개발하였다.

플레이어는 N행*M열의 카드로 이루어진 테이블을 받는다. 각각의 카드에는 동전의 앞면이 나올 확률이 적혀있다.(즉, i행, j열의 카드에는 동전ij의 앞면이 나올 확률이 적혀있다.)

모든 동전의 앞면이 나올 확률은 독립적이어서 서로 영향을 받지 않는다. 플레이어는 주어진 테이블에서 각 "열"마다 한장씩을 카드를 선택하여 N개의 세트를 만들어야 한다. 그리고, 각 세트별로 모든 동전이 앞면이 나왔을 때 1달러를 받는다(총 N달러를 받을 수 있음.)

오늘 카지노에서는 새로운 게임의 프로모션으로 모든 고객들에게 이 게임을 1회 무료로 제공하기로 하였다. 당신은 공짜라는 말에 이 게임을 한 번 해보기로 하였다. 이 게임에서 최대로 얻을 수 있는 기대값은 얼마인가?

- 예제

2 3 
1.0 1.0 1.0 
0.5 0.4 0.3 

• (1.0, 1.0, 1.0) - (0.5, 0.4, 0.3)
• (1.0, 1.0, 0.3) - (0.5, 0.4, 1.0)
• (1.0, 0.4, 1.0) - (0.5, 1.0, 0.3)
• (1.0, 0.4, 0.3) - (0.5, 1.0, 1.0)

The player is given a table on a card with N rows and M columns. Each entry ij of the table corresponds to a coin flip with a probability pij of coming up heads.

All the coin flips are independent of each other. The player must choose N sets of M entries, with each set having exactly one entry from each column, and each entry being used exactly once. For each chosen set where all M coins come up heads, the player wins 1 dollar.

The casino is feeling uncharacteristically generous, and so as part of the promotion of this new game, they have been handing out one card to each patron. Since you have nothing to lose, you're going to give this game a shot. How can you maximize your expected winnings from this card?

입력

• Each test case begins with a line with two integers N and M , 1 <= N <= 100, 1 <= M <= 10, separated by a space.
• This is followed by N lines with M space-separated numbers each, denoting the entries pij of the table.

출력

입출력 예

입력

2 3
1.0 1.0 1.0
0.5 0.4 0.3

출력

1.0600

출처:standford/2010/
번역:hanaban