Core Training (Small2)

Writing contest problems is hard, so we built an AI that comes up with new ideas for us. To make the AI as creative as possible, we gave it $N$ different cores, each with its own personality. Just like people, these cores may get distracted or corrupt or may refuse to work. The $i$-th core has a success probability $P_i$ of functioning properly. As long as at least $K$ of the cores function properly, the AI functions properly. Otherwise it probably becomes evil and traps us in a maze of fiendish puzzles of its own design. Who knows what it might do to the contest. It might write a pile of tough probability problems.

To prevent that, we plan to train one or more of the cores to become more reliable. We have $U$ training units in total. Spending $X$ units on the $i$-th core adds $X$ to its success probability. We can divide the units among the cores however we like, and some cores may receive no units at all. A success probability can never be raised above $1$.

If we assign the training units so that the probability that the AI functions properly is as large as possible, what is that probability?

The first line of the input gives the number of test cases, $T$. $T$ test cases follow, and each one consists of three lines.

The first line contains two integers $N$ and $K$: the total number of cores, and the minimum number of cores that must succeed for the AI to function properly. The second line contains one rational number $U$, the number of training units. The third line contains $N$ rational numbers, the $i$-th of which is the probability $P_i$ that the $i$-th core functions properly. $U$ and every probability are given with exactly four digits after the decimal point.

Limits

• $1 \le T \le 100$
• $1 \le N \le 50$
• $1 \le K \le N$
• $0.0000 \le P_i \le 1.0000$ for all $i$
• $0.0000 \le U \le N - (P_1 + P_2 + \dots + P_N)$ (there are never more training units than can be used)

For each test case, print one line of the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the probability that the AI functions properly when the training units are assigned optimally. Round $y$ at the seventh digit after the decimal point and print exactly six digits after the decimal point. For a probability of $0.25$ print 0.250000, and for a probability of $1$ print 1.000000.

In the first test case of the sample, we have enough training units to give every core a success probability of 1, so the AI certainly functions properly.

In the second test case, both cores must function properly, so each core needs some training units. The best option is to train each one up to $0.5$, which gives a probability of $0.5 \times 0.5 = 0.25$. Every other assignment is worse. Training one core to $0.9$ and the other to $0.1$ gives only $0.09$.

In the third test case there are no training units to spend, and at least one of the two cores must function properly. The AI fails only when both cores fail, and that happens with probability $(1 - 0.9) \times (1 - 0.8) = 0.02$, so the answer is $1 - 0.02 = 0.98$.

In the fourth test case the best strategy is to give all the training units to the second core. That makes the probability that at least one core functions properly $1 - (0.6 \times 0.4) = 0.76$. All other options are worse: giving all the units to the first core yields $0.75$, and dividing them equally between the cores gives $0.7525$.