Algorithms
The Macedonian IOI team consists of very smart contestants. If only they were to spend more of their time practicing, they could end up winning a lot of medals at international competitions in informatics.
Emil is the team leader of the Macedonian team, and he's struggling to find a way to make his students practice. In his latest attempt, he found a list of thousands of old competitions in informatics, ordered by time (from the oldest competitions, to the newest). For each competition, he has indicated what kinds of tasks were presented there (for every task he indicates the algorithm needed to solve it). All competitions in the list have the same number of tasks.
Task 1 | Task 2 | Task 3 | |
Competition #1. | DFS | DP | BF |
Competition #2. | SP | DFS | DP |
Competition #3. | BF | BF | DFS |
Competition #4. | SP | BF | DP |
Emil plans to organize a training camp where he will explain exactly M algorithms to his students. As a homework, after the camp, Emil plans to give them a sequence of several consecutive competitions from the list he found, so that in each competition in the sequence there is at least one of the algorithms explained on the camp. In order to give the students a longer sequence of competitions, Emil will choose the M algorithms so that the sequence is as long as possible.
Please, write a program that will identify which is the longest sequence of consecutive competitions (that satisfies the requirements given above) and output the number of competitions in it.
For example, for the table of competitions and tasks presented above and M=2, Emil would choose the algorithms {DFS, BF}. That way, students will need to solve tasks from all 4 competitions on the list, because in each one of those competitions, there is at least one task of type DFS or BF.
Input
The first line of input contains three integers N (1 <= N <= 100 000), the number of competitions, T (1 <= T <= 4), the number of tasks on each competition, and M (1 <= M <= 3), the necessary number of algorithms.
In each of the next N lines, there are T strings Aij, each consisting of at most 10 uppercase letters 'A' - 'Z' separated by a single space. These strings denote the algorithms needed to solve the tasks given at each of the N competitions in Emil's list.
Note: Two different algorithms are represented by two different strings.
Output
In the first line of output, print the number of competitions in the longest sequence. Have in mind that Emil makes an optimal choice of algorithms, as described in the problem statement.
Constraints
Time limit: 2 seconds
Memory limit: 256 megabytes
Examples
input 4 3 2 DFS DP BF SP DFS DP BF BF DFS SP BF DP | output 4 |
input 7 2 1 DFS BF DFS XYZ BFS SP ABC ABC SP BFS BFS SP BFS BFS | output 3 |
Scoring
- In test cases worth at least 10% of all points, 1 <= N <= 1 000 and M = 1.
- In test cases worth an additional 10% of all points, 1 <= N <= 100 000 and M = 1.
- In test cases worth an additional 40% of all points, M = 2.