베팅 세트

면접 대비

시간 제한1초메모리 제한128 MB

요약

각 열에서 하나씩 뽑아 N개의 그룹으로 나눌 때, 모든 동전이 앞면인 그룹 수의 기댓값이 최대가 되도록 배정하는 문제이다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 비트 연산, 조합론, 그리디
정답자: 아직 제출이 없습니다

문제

한 카지노가 새로운 베팅 게임을 선보였습니다. $N$ 개의 행과 $M$ 개의 열로 이루어진 표가 주어집니다. $i$ 행 $j$ 열의 칸에는 앞면이 나올 확률이 $p_{ij}$ 인 동전이 하나 놓여 있으며, 모든 동전 던지기는 서로 독립입니다.

표의 모든 칸을 $N$ 개의 그룹으로 나누어야 합니다. 각 그룹은 모든 열에서 정확히 한 칸씩을 포함하고, 표의 각 칸은 정확히 하나의 그룹에만 속합니다(즉, 한 열의 $N$ 개 칸은 그룹마다 하나씩 배분됩니다). 어떤 그룹에서 $M$ 개의 동전이 모두 앞면이 나오면 1달러를 얻습니다.

기대 상금이 최대가 되도록 그룹을 구성했을 때, 그 최대 기대 상금을 구하세요.

입력

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스의 첫 줄에는 두 정수 $N$ 과 $M$ 이 주어집니다 ( $1 \le N \le 100$ , $1 \le M \le 10$ ). 이어지는 $N$ 개의 줄에는 각각 $M$ 개의 실수가 공백으로 구분되어 주어지며, 이는 표의 값 $p_{ij}$ 입니다. 입력의 끝은 $N = M = 0$ 인 줄로 표시되며, 이 줄은 처리하지 않습니다.

출력

각 테스트 케이스마다, 해당 표에서 얻을 수 있는 최대 기대 상금을 소수점 넷째 자리까지 반올림하여 한 줄에 출력하세요.

예제3

예제 1
입력
```
2 3
1.0 1.0 1.0
0.5 0.4 0.3
0 0
```
예상 출력
```
1.0600
```
예제 2
입력
```
3 2
0.2 0.6
0.9 0.1
0.5 0.8
0 0
```
예상 출력
```
1.0400
```

예제 3

입력

예상 출력

0.5000
1.0000