AT_past202209_g.Wildcards

设 $S$ 为一个仅包含小写英文字母的字符串，$T$ 为一个仅包含小写英文字母和 ? 的字符串。
当可以将 $T$ 中的每个 ? 替换为某个小写英文字母，从而使 $T$ 等于 $S$ 时，称 $S$ 可以“通过 $T$ 得到”。

例如，abcd 和 addd 都可以通过 a??d 得到，而 bcdd 不行。

现给定 $N$ 个小写英文字母字符串 $S_1, S_2, \ldots, S_N$，
所有这些字符串的长度均为 $L$，即 $|S_1| = |S_2| = \cdots = |S_N| = L$。

现从所有长度为 $L$、恰好包含 $K$ 个 ? 的小写字母字符串 $T$ 中任选一个。
请你求出，在这些 $T$ 中，最多能有多少个字符串 $S_1, S_2, \ldots, S_N$ 能通过 $T$ 得到。

输入格式如下：

$N$ $L$ $K$
$S_1$
$S_2$
$\vdots$
$S_N$

输出一个整数，表示最大可得到的字符串数量。

样例解释 1

若令 $T = $ a?b?，则 $S_1 = $ aabc、$S_3 = $ abbc、$S_5 = $ acba 都可以通过 $T$ 得到。这里，$S_1, S_2, \ldots, S_N$ 中有 $3$ 个字符串可以通过 $T$ 得到，这就是最大可能值。注意 $K = 2$，所以 $T$ 必须恰好有两个 ?。

样例解释 2

若令 $T = $ ????，则 $S_1, S_2, S_3, S_4, S_5$ 都可以通过 $T$ 得到。

数据范围

• $1 \leq N \leq 1000$
• $1 \leq L \leq 10$
• $0 \leq K \leq L$
• $N, L, K$ 均为整数。
• $S_1, S_2, \ldots, S_N$ 均为长度为 $L$ 的小写字母字符串。
• $S_1, S_2, \ldots, S_N$ 互不相同。

由 ChatGPT 5 翻译