레드 테이프 위원회 (Large)

당신은 중복감축 및 불필요축소부의 부장이다. 지금 부서 안에서는 이 부서 자체에 "레드 테이프"(비효율)가 너무 많은지를 두고 의견이 갈린다. 부서원들은 당신에게 이 문제를 투표로 결정할 레드 테이프 위원회를 구성해 달라고 요청했다.

부서원은 $N$명이다. 각 부서원 $i$가 "찬성"에 투표할 확률 $P_i$를 알고 있다. "찬성"에 투표하지 않은 부서원은 반드시 "반대"에 투표하며, 기권하는 사람은 없다.

위원회에는 정확히 $K$명을 뽑아야 한다. 부서 규정상 동수가 나올 수 있도록 $K$는 짝수여야 한다. 동수는 건강한 관료제의 일부로 여겨진다.

동수가 나올 확률이 최대가 되도록 위원을 뽑을 때, 그 확률을 구하라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어지며, 각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에는 부서의 인원 $N$과 위원회의 인원 $K$가 주어진다. 둘째 줄에는 $N$개의 실수 $P_i$가 주어진다. 각 값은 소수점 아래 정확히 두 자리이며, $i$번째 부서원이 "찬성"에 투표할 확률을 나타낸다.

• $1 \le T \le 100$
• $2 \le K \le N \le 200$
• $K$는 짝수이다.
• $0.00 \le P_i \le 1.00$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 동수가 나올 수 있는 최대 확률이다. y는 반올림하여 소수점 아래 정확히 여섯 자리로 출력한다(예: 0.500000).

첫 번째 예제에서는 부서원 두 명을 모두 위원으로 뽑아야 한다. 두 사람의 투표가 다를 때만 동수가 되고, 그 확률은 절반이다. (일반성을 잃지 않고 첫 번째 사람의 투표를 고정하면, 두 번째 사람이 반대로 투표할 확률은 0.5이다.)

두 번째 예제에서 최선은 "찬성" 확률이 0.00인 부서원 한 명과 1.00인 부서원 한 명을 뽑는 것이다. 이렇게 하면 반드시 동수가 된다.

세 번째 예제에서 "찬성" 확률이 0.50과 0.75인 두 사람을 뽑았다고 하자. 첫 번째 사람이 "찬성", 두 번째 사람이 "반대"에 투표하면(확률 $0.5 \times 0.25 = 0.125$) 동수가 되고, 첫 번째 사람이 "반대", 두 번째 사람이 "찬성"에 투표해도(확률 $0.5 \times 0.75 = 0.375$) 동수가 된다. 따라서 동수가 될 확률은 $0.125 + 0.375 = 0.5$이다. 확률이 0.50과 1.00인 두 사람을 뽑아도 1.00인 사람은 "찬성"에 투표하므로 0.50인 사람이 "반대"에 투표해야 하고, 동수 확률은 역시 0.5이다. 확률이 0.75와 1.00인 두 사람을 뽑으면 0.75인 사람이 "반대"에 투표해야 하므로 동수 확률은 0.25에 그친다. 따라서 0.5가 최선이다.