P16622 [GKS 2017 #C] Magical Thinking v2

你和 $N$ 个朋友刚刚参加了 B.A.T.（二进制答案测试），试图进入魔法学校。B.A.T. 有 $Q$ 道是非题，每题 1 分。你没有魔法能力，所以只是随意选择答案，听天由命。 测试结果已通过鹌鹑邮件寄出，但载有你成绩的那只鹌鹑尚未到达。不过，你的每个朋友都告诉了你他们的答案列表以及总分。你也记得自己的答案列表。你是个乐观主义者，觉得自己可能考得不错！ 给定存在一份正确的答案列表（但你不知道具体是什么），并给定你朋友的答案与分数，请问你有可能获得的最高分数是多少？

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $Q$。随后有 $N+1$ 行，其中第 $i$ 行表示第 $i$ 个考生的答案列表 $A_i$，包含 $Q$ 个字符，每个字符为 `T` 或 `F`（分别表示真或假）。$A_{N+1}$ 是你自己的答案列表。最后一行包含 $N$ 个整数，其中第 $i$ 个整数 $S_i$ 表示第 $i$ 个考生的得分。（注意，你自己的得分不在此列表中，因为未知。）

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是与给定信息一致的前提下你有可能获得的最高分数。

请注意，最后一个样例不会出现在小数据集中。 在样例 #1 中，你的朋友作答为 `TF`，你作答为 `FF`，且你的朋友恰好答对一题。如果你的朋友在第 1 题错误、第 2 题正确，则真实答案列表为 `FF`，你两题都答对了。不可能做得比这更好！ 在样例 #2 中，你的朋友全部答 `T` 且全部错误，因此真实答案列表必须全部是 `F`，这意味着你只答对了第 3 题。 在样例 #3 中，与给定信息一致的可能真实答案列表只有 `FTT` 和 `FFF`。（例如，真实答案列表不可能是 `TFT`：第一个朋友的答案与得分会与此一致，但第二个朋友的得分将是 0 而不是 2。）在这两种可能性中，`FTT` 对你更有利，你能得到 2 分。 ### 限制条件 $1 \le T \le 100$。 对于所有 $i$，$A_i$ 的长度均为 $Q$。 对于所有 $i$，$A_i$ 的每个字符均为 `T` 或 `F`。 $0 \le S_i \le Q$。 保证至少存在一种与所有朋友的答案及得分一致的正确答题列表。 **小数据集（测试集 1 – 可见）** $N = 1$。 $1 \le Q \le 10$。 **大数据集（测试集 2 – 隐藏）** $1 \le N \le 2$。 $1 \le Q \le 50$。 翻译由 DeepSeek V4 Pro 完成