영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
The school administration has encountered a problem with the upcoming graduation, a problem they hope you can help them solve. During the graduation, students will be lined up in N rows, with M students in each row. The administration wants the graduation to be as colorful as possible and will therefore distribute hats in different colors to the students.
To make the lineup look nice, it is important that all students in the same column have the same hat color. To ensure that nobody feels left out, it is also important that all students in the same class have the same hat color. The row and column for each student are already determined, but not the hat color. The administration needs your help in assigning hat colors to the students to make the graduation as colorful as possible.
Please help the school administration to calculate the maximum number of unique hat colors that can be assigned to the students given how the students will be lined up at the graduation.
Input
The first line of the input contains three integers N, M and K (1 ≤ N,M ≤ 700, 1 ≤ K ≤ 26), the number of rows, the number of columns and the number of classes.
The following N lines each contain a string consisting of M characters, which describes how the students will be positioned during the graduation. Each character will be an uppercase letter between A and the K:th letter in the alphabet. Each character indicates the class that the student at that particular position belongs to. There is at least one student belonging to each class.
Output
Print an integer: the largest number of distinct colors of hats that the school administration can use, while ensuring that each column has the same hat color, and that all students from the same class get the same hat color.
Points
Your solution will be tested on several test case groups. To get the points for a group, it must pass all the test cases in the group.
| Group | Point value | Constraints |
|---|---|---|
| 1 | 15 | N, M ≤ 5 |
| 2 | 15 | K = 2 |
| 3 | 35 | N, M ≤ 50 |
| 4 | 35 | No further constraints. |
Explanation of samples
In the first example, one student from class A and one from class B are in the second column. Since both of these students must have the same color on their hats, the entirety of class A must have the same color as class B. Thus, it follows that all students at the graduation must have the same color, which makes the answer 1.
In the second example, class A and class B must have the same color, as there is one student from each of these two classes in the first column. However, class C can have a different color for their hats. The answer then becomes 2.
In the third example, we can assign each class a different color since there are no two students from different classes in the same column. The answer is 3.
In the last example, we can assign all students from class A, B, and C one color, and all students from class D and E another color. The answer is 2.
예제
예제 1
2 3 2 AAB ABB
1
예제 2
2 2 3 AC BC
2
예제 3
2 3 3 ABC ABC
3
예제 4
3 5 5 ABECE BCDAE CADBD
2