Description

Dave 正在互联网上参加一场多项选择题测试。Dave 可能有多次提交答案的机会，但只有当他所有问题都答对时才算通过。他必须回答测试中的每一个问题才能提交。每次提交后，他唯一能得到的信息是自己是否通过了测试。

对于每一道题，他会估计每个选项为正确答案的概率，这些概率与他对其他题目的回答无关。给定他可以提交的次数 $M$，Dave 想要选择答案，使得通过测试的概率最大。

如果 Dave 最优地选择答案，他通过测试的概率是多少？

Input Format

第一行输入一个整数 $C$，表示测试用例的数量。接下来有 $C$ 组测试数据。

每组测试数据的第一行包含两个整数 $M$ 和 $Q$，分别表示 Dave 可以提交的次数和测试题目的数量。接下来的 $Q$ 行，每行包含 4 个概率值，分别表示每个选项为正确答案的概率。每行的概率值最多有 6 位小数，且非负且和为 1。

Output Format

对于每组测试数据，输出一行，格式为 “Case #$X$: $Y$”，其中 $X$ 是测试用例编号（从 1 开始），$Y$ 是通过测试的最大概率。

当答案的相对或绝对误差不超过 $10^{-6}$ 时，视为正确。

3
10 2
0.25 0.25 0.25 0.25
0.25 0.25 0.25 0.25
64 3
0.3 0.4 0.0 0.3
1.0 0.0 0.0 0.0
0.2 0.2 0.2 0.4
3 2
0.5 0.17 0.17 0.16
0.5 0.25 0.25 0.0

Case #1: 0.625
Case #2: 1.0
Case #3: 0.5

Hint

数据范围

• $1 \leqslant C \leqslant 100$

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

• 时间限制：6 秒。
• $1 \leqslant Q \leqslant 6$
• $1 \leqslant M \leqslant 1000$

大数据集（测试集 2 - 隐藏）

• 时间限制：18 秒。
• $1 \leqslant Q \leqslant 30$
• $1 \leqslant M \leqslant 10000$

由 ChatGPT 4.1 翻译