Core Training (All Cores)

An AI runs on $N$ cores, and every core has a personality of its own. Like people, a core can get distracted, break down, or simply refuse to work. Core $i$ works properly with probability $P_i$. If at least $K$ cores work properly, the AI works properly. Otherwise the AI starts doing something else entirely.

To stop that, you train some of the cores to make them more reliable. You have $U$ training units in total. Spending $X$ units on core $i$ raises that core's success probability by $X$. You may split the units among the cores any way you like, in real amounts, and a core may receive nothing at all. A success probability can never rise above $1$.

Compute the probability that the AI works properly when the training units are assigned optimally.

In this problem $K = N$ always holds. If even one core fails, the AI does not work properly.

The first line contains the number of test cases $T$. Then $T$ test cases follow, each on three lines. The first line contains two integers $N$ and $K$: the number of cores, and the minimum number of cores that must succeed for the AI to work properly. The second line contains $U$, the total amount of training units. The third line contains $N$ numbers, the $i$-th of which is the success probability $P_i$ of core $i$. Both $U$ and every $P_i$ are written with exactly four digits after the decimal point.

Limits

• $1 \le T \le 100$
• $1 \le N \le 50$
• $0.0000 \le P_i \le 1.0000$ for every $i$
• $0.0000 \le U \le N - \sum_{i=1}^{N} P_i$ (there are never more training units than can be used)
• $K = N$

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 works properly under an optimal assignment of the training units.

Print $y$ with exactly six digits after the decimal point, rounding the seventh digit onward to the nearest value and rounding up on an exact half. Print all six digits even when they are zeros. A probability of $1$ prints as 1.000000, and $1/4$ prints as 0.250000.

In the first case of the first example there are enough training units to raise all four cores to probability $1$, so the answer is $1$.

In the second case of the first example both cores have to succeed, so both of them get units. Raising each one to $0.5$ is best and gives $0.5 \times 0.5 = 0.25$. Training one core to $0.9$ and the other to $0.1$ yields only $0.09$.

In the third case of the second example all $0.2$ units go to the weaker core, raising $0.1$ to $0.3$. The answer is $0.3 \times 0.9 = 0.27$. Giving every unit to the stronger core wastes part of them because a probability cannot exceed $1$, which leaves $0.1 \times 1.0 = 0.1$, and splitting the units evenly gives $0.2 \times 1.0 = 0.2$.