题目描述

你和 $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$ 是与给定信息一致的前提下你有可能获得的最高分数。

3
1 2
TF
FF
1
1 3
TTT
TTF
0
2 3
TTF
FTF
TTT
1 2

Case #1: 2
Case #2: 1
Case #3: 2

提示

请注意，最后一个样例不会出现在小数据集中。

在样例 #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 完成