Red Tape Committee (Large)

You are the head of the Department of Redundancy Reduction and Superfluity Shrinkage. Currently, the department cannot agree on whether there is too much "red tape" (inefficiency) in the department itself. They have asked you to form a Red Tape Committee to vote on the issue.

The department has $N$ members. For each member $i$, you know the probability $P_i$ that the member will vote "Yes". A member who does not vote "Yes" necessarily votes "No"; nobody abstains.

You must choose exactly $K$ members to be on the committee. The department rules require $K$ to be even so that ties are possible, since ties are seen as part of a healthy bureaucracy.

If you choose the committee members to maximize the probability of a tie, what is that probability?

The first line of the input gives the number of test cases, $T$. $T$ test cases follow, each on two lines. The first line of a test case contains two integers $N$ and $K$, the sizes of the department and the committee. The second line contains $N$ decimal values $P_i$. Each value has exactly two digits after the decimal point and is the probability that the $i$-th department member votes "Yes".

• $1 \le T \le 100$
• $2 \le K \le N \le 200$
• $K$ is even.
• $0.00 \le P_i \le 1.00$

For each test case, output one line of the form Case #x: y, where x is the test case number (starting from 1) and y is the maximum possible probability of a tie. Print y rounded to exactly six digits after the decimal point (for example, 0.500000).

In sample case #1, you must put both department members on the committee. The committee ties only if the two members vote differently, which happens half the time. (Fix the vote of the first member. The probability that the second member votes the other way is 0.5.)

In sample case #2, the best strategy is to pick one member with "Yes" probability 0.00 and one member with "Yes" probability 1.00. This guarantees a tie.

In sample case #3, suppose we pick the two members with "Yes" probabilities 0.50 and 0.75. A tie happens if the first votes "Yes" and the second votes "No" (probability $0.5 \times 0.25 = 0.125$), or if the first votes "No" and the second votes "Yes" (probability $0.5 \times 0.75 = 0.375$). The total probability of a tie is $0.125 + 0.375 = 0.5$. Choosing the members with probabilities 0.50 and 1.00 also gives 0.5, because the 1.00 member votes "Yes" and the 0.50 member must vote "No". Choosing the members with probabilities 0.75 and 1.00 gives only 0.25, because the 1.00 member votes "Yes" and the 0.75 member must vote "No". So 0.5 is the best possible.