编写 Code Jam 题目是一件困难的事，因此我们构建了一个人工智能（AI）来构思新点子。为了让 AI 尽可能具有创造力，我们给了它 $N$ 个不同的“核心”，每个核心都有其独特的“个性”。然而，就像人一样，这些核心可能会分心、损坏或拒绝工作；第 $i$ 个核心正常工作的成功概率为 $P_i$。只要至少有 $K$ 个核心正常工作，AI 就能正常工作。否则，它可能会变坏，并把我们困在它自己设计的恶魔般的谜题迷宫中。谁知道它会对 Code Jam 做什么呢——它可能只会写出一堆难题！

为了防止这种情况发生，我们计划训练一个或多个核心，使其变得更可靠。我们总共有 $U$ 个“训练单元”可以用来改进核心。在第 $i$ 个核心上花费 $X$ 个单元，会将其成功概率增加 $X$。我们可以随意分配这些单元，也可以让一个或多个核心不接收任何单元。当然，核心的成功概率不能超过 1。

如果我们分配这些训练单元以最大化 AI 正常工作的概率，那么这个概率是多少？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例；每个测试用例包含三行。第一行包含两个整数 $N$ 和 $K$：核心的总数，以及 AI 正常工作所需的最少核心数。第二行包含一个有理数 $U$：训练单元的数量。第三行包含 $N$ 个有理数 $P_i$；其中第 $i$ 个数表示第 $i$ 个核心正常工作的概率。所有这些概率都精确到小数点后四位。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是在最优分配训练单元的情况下，AI 正常工作的概率。如果 $y$ 与正确答案的绝对误差或相对误差在 $10^{-6}$ 以内，则视为正确。

数据范围

$1 \le T \le 100$ $1 \le N \le 50$ 对于所有 $i$，$0.0000 \le P_i \le 1.0000$ $0.0000 \le U \le N - \sum P_i$（训练单元总数不会超过可使用的上限）

小数据 1（可见测试集 1）

$K = N$ （所有核心都必须正常工作，AI 才能正常工作。）

小数据 2（可见测试集 2）

$1 \le K \le N$

样例

样例输入 1

4
4 4
1.4000
0.5000 0.7000 0.8000 0.6000
2 2
1.0000
0.0000 0.0000
2 1
0.0000
0.9000 0.8000
2 1
0.1000
0.4000 0.5000

样例输出 1

Case #1: 1.000000
Case #2: 0.250000
Case #3: 0.980000
Case #4: 0.760000

说明

注意，最后两个样例不会出现在小数据 1 中。

在样例 1 中，我们有足够的训练单元将所有核心的成功概率提升至 1，因此 AI 一定会正常工作。

在样例 2 中，两个核心都必须正常工作，AI 才能正常工作，因此我们必须给每个核心分配一些训练单元。最优方案是将每个核心的概率都提升至 0.5。此时 AI 正常工作的概率为 $0.5 \times 0.5 = 0.25$。任何其他分配方式都不如该方案；例如，如果我们训练一个核心到 0.9，另一个到 0.1，成功概率仅为 $0.9 \times 0.1 = 0.09$。

在样例 3 中，我们没有训练单元可供使用，且两个核心中至少有一个必须正常工作，AI 才能正常工作。我们可以先计算 AI 不正常工作的概率，这种情况仅在两个核心都失败时发生。两个核心都失败的概率为 $(1 - 0.9) \times (1 - 0.8) = 0.02$。因此，至少有一个核心正常工作（即 AI 正常工作）的概率为 $1 - 0.02 = 0.98$。

在样例 4 中，最优策略是将所有训练单元分配给第二个核心。这使得至少有一个核心正常工作的概率为 $1 - (0.4 \times 0.6) = 0.76$。所有其他选项都不如该方案；例如，将所有训练单元给第一个核心只能得到 0.75，而平均分配给两个核心则得到 0.7525。