← 返回题目列表

AtCoder · past202209_g

G. 通配符

中文机器翻译题面 查看原题

分数: 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