시험 합격 확률

Dave는 인터넷에서 객관식 시험을 치르고 있다. Dave에게는 시험 답안을 제출할 기회가 여러 번 주어질 수도 있지만, 모든 문제를 맞혀야만 합격한다. 답안을 제출하려면 시험의 모든 문제에 답해야 한다. 제출 후에 받는 정보는 합격했는지 여부뿐이다.

각 문제에 대해 Dave는 4개의 응답 각각이 정답일 확률을 추정하며, 이 확률은 다른 문제에 대한 응답과 독립적이다. 제출할 수 있는 횟수가 고정되어 있을 때, Dave는 시험에 합격할 확률을 최대화하도록 응답을 선택하려 한다.

Dave가 응답을 최적으로 선택할 때 시험에 합격할 확률은 얼마인가?

제한

메모리 제한: 1GB. 1 ≤ C ≤ 100

작은 데이터 세트(테스트 세트 1 - 공개)

시간 제한: 60초. 1 ≤ Q ≤ 6 1 ≤ M ≤ 1000

큰 데이터 세트(테스트 세트 2 - 비공개)

시간 제한: 180초. 1 ≤ Q ≤ 30 1 ≤ M ≤ 10000

입력의 첫 번째 줄에는 케이스 수 C가 주어진다. 이어서 C개의 테스트 케이스가 주어진다.

각 테스트 케이스는 M과 Q가 담긴 한 줄로 시작한다. Dave는 시험을 풀기 위해 M번 답안을 제출할 수 있다. 시험에는 Q개의 문제가 있다. 이어지는 Q개의 줄에는 각각 정답일 확률 4개가 주어진다. 소수점 뒤에는 최대 6개의 숫자가 주어진다. 각 줄의 확률은 음이 아니며, 그 합은 1이다.

각 테스트 케이스마다 "Case #X: Y"을 담은 한 줄을 출력한다. 이때 X는 1부터 시작하는 테스트 케이스 번호이고, Y는 성공 확률이다. 상대 오차 또는 절대 오차가 최대 10^{−6}인 답은 정답으로 인정된다.