题目描述

中国的奶茶非常美味。定制一杯奶茶时有许多二选一的选项，例如“加冰/不加冰”、“加糖/不加糖”、“加珍珠/不加珍珠”、“加布丁/不加布丁”等等。顾客对奶茶的偏好可以用一个二进制字符串表示。例如，使用上述四个属性（按给出的顺序），字符串 1100 表示“加冰、加糖、不加珍珠、不加布丁”。

今天，Shakti 负责为他的 $N$ 个朋友每人买一杯奶茶，奶茶店提供 $P$ 个二进制选项。但在收集了所有人的偏好后，Shakti 发现订单变得过于复杂，因此他决定为所有人购买同一种类型的奶茶。Shakti 知道，对于每个朋友，每有一个偏好未被满足，他们就会抱怨一次。例如，如果有两个朋友的偏好分别为 101 和 010，而 Shakti 选择了类型 001，那么第一个朋友会抱怨一次，第二个朋友会抱怨两次，总共三次抱怨。

此外，有 $M$ 种不同的奶茶类型是奶茶店不制作的，Shakti 不能选择这些被禁止的类型。

Shakti 能得到的最少抱怨次数是多少？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含三个整数 $N$、$M$ 和 $P$，含义如上所述。随后有 $N$ 行，每行包含一个二进制字符串，表示 $N$ 个朋友的偏好。最后有 $M$ 行，每行包含一个二进制字符串，表示奶茶店不制作的被禁止类型。二进制字符串仅由字符 0 和/或 1 组成。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Shakti 能获得的最少抱怨次数，按照上述规则。

2
3 1 4
1100
1010
0000
1000
2 4 4
1111
1111
1111
0111
1011
1101

Case #1: 4
Case #2: 2

提示

在样例 #1 中，有 3 个朋友，他们想要的奶茶类型分别是 1100、1010 和 0000。如果 Shakti 可以选择类型 1000，那么每个朋友会抱怨一次，总共 3 次抱怨。然而，奶茶店不制作 1000 类型。因此，在给定约束下，最优解是选择类型 1100。这样，他的朋友们分别抱怨 0、2 和 2 次，总共 4 次抱怨。

在样例 #2 中，Shakti 的最佳选择是类型 1110。每个朋友会抱怨一次，总共 2 次抱怨。注意，不同的朋友可能有相同的偏好。同时请注意，小数据集和大数据集的限制都保证至少存在一种不被禁止的奶茶类型。

限制条件

$1 \le T \le 100$。

所有被禁止的奶茶类型互不相同。

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

$1 \le N \le 10$。

$1 \le M \le \min(10, 2^P - 1)$。

$1 \le P \le 10$。

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

$1 \le N \le 100$。

$1 \le M \le \min(100, 2^P - 1)$。

$1 \le P \le 100$。

翻译由 DeepSeek V4 Pro 完成