P13480 [GCJ 2008 AMER SemiFinal] Test Passing Probability

Dave 正在互联网上参加一场多项选择题测试。Dave 可能有多次提交答案的机会，但只有当他所有问题都答对时才算通过。他必须回答测试中的每一个问题才能提交。每次提交后，他唯一能得到的信息是自己是否通过了测试。 对于每一道题，他会估计每个选项为正确答案的概率，这些概率与他对其他题目的回答无关。给定他可以提交的次数 $M$，Dave 想要选择答案，使得通过测试的概率最大。 如果 Dave 最优地选择答案，他通过测试的概率是多少？

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

对于每组测试数据，输出一行，格式为 “Case #$X$: $Y$”，其中 $X$ 是测试用例编号（从 1 开始），$Y$ 是通过测试的最大概率。 当答案的相对或绝对误差不超过 $10^{-6}$ 时，视为正确。

**数据范围** - $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 翻译