分数: 6 点
问题陈述
让 S 为小写英文字母组成的字符串, T 为小写英文字母组成的字符串, ?.
S 据说是 可从 T 当一个人可以替换每个出现的 ? in T 带有一些小写英文字母,以便 T 等于 S.
例如, abcd 和 addd 可从 a??d,同时 bcdd 不是。
你被给予 N 字符串 S_1, S_2, \ldots, S_N 由小写英文字母组成。
所有这些字符串的长度均为
任意选择由小写英文字母组成的 L: |S_1| = |S_2| = \cdots = |S_N| = L.
一个字符串 T 长度 L ,以便 恰好包含 K ?s.
找出其中最大可能的字符串数 S_1, S_2, \ldots, S_N 可从 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 是不同的。
输入
输入由标准输入按以下格式给出:
N L K S_1 S_2 \vdots S_N
输出
打印答案。
示例输入 1
5 4 2 aabc bbaa abbc cccc acba
示例输出 1
3
如果我们让 T = a?b?,那么 S_1 = aabc, S_3 = abbc,和 S_5 = acba 可从 T。
这里,三个字符串 S_1, S_2, \ldots, S_N 可从 T,这是可能的最大数量。
请注意 K = 2,所以 T 必须选择包含正好两个 ?s。
示例输入 2
5 4 4 aabc bbaa abbc cccc acba
示例输出 2
5
如果我们让 T = ????,全部 S_1, S_2, S_3, S_4, S_5 可从 T.
示例输入 3
5 4 0 aabc bbaa abbc cccc acba
示例输出 3
1