/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 6 点
問題文
S を英小文字のみからなる文字列、T を英小文字および ? のみからなる文字列とします。
T に含まれる ? をそれぞれ適切な英小文字 1 つで置き換えることで、T を S に一致させることができるとき、「 S は T から作れる」と言います。
例えば、a??d からは abcd や addd を作れますが bcdd を作ることはできません。
英小文字のみからなる N 個の文字列 S_1, S_2, \ldots, S_N が入力として与えられます。
これらの長さはすべて L です。すなわち、|S_1| = |S_2| = \cdots = |S_N| = L です。
文字列 T として、英小文字および ? からなる長さ L の文字列であって ? をちょうど K 個含むものを任意に選びます。
「 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 の 3 つを T から作れます。
このとき「 S_1, S_2, \ldots, S_N のうち、T から作れるものの個数」は 3 であり、これがあり得る最大値となります。
K = 2 より、T は ? をちょうど 2 個含むように選ばれなければならないことに注意してください。
入力例 2
5 4 4 aabc bbaa abbc cccc acba
出力例 2
5
T = ???? とすると、S_1, S_2, S_3, S_4, S_5 のすべてを作れます。
入力例 3
5 4 0 aabc bbaa abbc cccc acba
出力例 3
1
Score : 6 points
Problem Statement
Let S be a string consisting of lowercase English letters and T be a string consisting of lowercase English letters and ?.
S is said to be obtainable from T when one can replace each occurrence of ? in T with some lowercase English letter so that T equals S.
For example, abcd and addd are obtainable from a??d, while bcdd is not.
You are given N strings S_1, S_2, \ldots, S_N consisting of lowercase English letters.
All of these strings have a length of L: |S_1| = |S_2| = \cdots = |S_N| = L.
A string T of length L consisting of lowercase English letters is arbitrarily chosen so that it contains exactly K ?s.
Find the maximum possible number of strings among S_1, S_2, \ldots, S_N that are obtainable from T.
Constraints
- 1 \leq N \leq 1000
- 1 \leq L \leq 10
- 0 \leq K \leq L
- N, L, and K are integers.
- Each of S_1, S_2, \ldots, S_N is a string of length L consisting of lowercase English letters.
- S_1, S_2, \ldots, S_N are distinct.
Input
Input is given from Standard Input in the following format:
N L K S_1 S_2 \vdots S_N
Output
Print the answer.
Sample Input 1
5 4 2 aabc bbaa abbc cccc acba
Sample Output 1
3
If we let T = a?b?, then S_1 = aabc, S_3 = abbc, and S_5 = acba are obtainable from T.
Here, three of the strings S_1, S_2, \ldots, S_N are obtainable from T, which is the maximum possible number.
Note that K = 2, so T must be chosen to contain exactly two ?s.
Sample Input 2
5 4 4 aabc bbaa abbc cccc acba
Sample Output 2
5
If we let T = ????, all of S_1, S_2, S_3, S_4, S_5 are obtainable from T.
Sample Input 3
5 4 0 aabc bbaa abbc cccc acba
Sample Output 3
1