졸업식

학교 행정부는 다가오는 졸업식과 관련하여 문제에 봉착했으며, 여러분이 이 문제를 해결해 주기를 바라고 있다. 졸업식 동안 학생들은 $N$개의 줄에 줄지어 서며, 각 줄에는 $M$명의 학생이 선다. 행정부는 졸업식을 가능한 한 다채롭게 만들고자 하므로 학생들에게 서로 다른 색의 모자를 나누어 줄 것이다.

대열이 보기 좋도록 같은 열에 있는 모든 학생이 같은 색의 모자를 쓰는 것이 중요하다. 아무도 소외감을 느끼지 않도록 같은 반의 모든 학생이 같은 색의 모자를 쓰는 것 또한 중요하다. 각 학생이 설 행과 열은 이미 정해져 있지만, 모자 색은 정해지지 않았다. 행정부는 졸업식을 가능한 한 다채롭게 만들 수 있도록 학생들에게 모자 색을 배정하는 데 여러분의 도움이 필요하다.

졸업식에서 학생들이 서게 될 대열이 주어질 때, 학생들에게 배정할 수 있는 서로 다른 모자 색의 최대 개수를 학교 행정부가 계산할 수 있도록 도와주자.

배점

여러 테스트 케이스 그룹으로 여러분의 풀이를 채점한다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한 조건

$1$ |$15$| $N, M \leq 5$

$2$ |$15$| $K = 2$

$3$ |$35$| $N, M \leq 50$

$4$ |$35$| 추가 제한 조건이 없다.

입력의 첫째 줄에는 세 정수 $N, M$와 $K$가 주어진다. ($1 \leq N,M \leq 700$, $1 \leq K \leq 26$) 이는 각각 행의 수, 열의 수, 반의 수이다.

이어지는 $N$개의 줄에는 각각 학생들이 졸업식에서 어떻게 배치될지를 나타내는, $M$개의 문자로 이루어진 문자열이 주어진다. 각 문자는 A부터 알파벳의 $K$:번째 글자까지의 대문자이다. 각 문자는 해당 위치의 학생이 속한 반을 나타낸다. 각 반에는 적어도 한 명의 학생이 속한다.

각 열의 학생들이 같은 색의 모자를 쓰고 같은 반의 모든 학생이 같은 색의 모자를 쓰도록 하면서 학교 행정부가 사용할 수 있는 서로 다른 모자 색의 최대 개수를 나타내는 정수를 출력한다.

첫 번째 예제에서는 A반 학생 한 명과 B반 학생 한 명이 두 번째 열에 있다. 이 두 학생은 모자 색이 같아야 하므로 A반 전체가 B반과 같은 색의 모자를 써야 한다. 따라서 졸업식의 모든 학생이 같은 색의 모자를 써야 하며, 답은 $1$가 된다.

두 번째 예제에서는 서로 다른 두 반의 학생이 첫 번째 열에 한 명씩 있으므로 A반과 B반은 같은 색의 모자를 써야 한다. 하지만 C반의 모자는 다른 색이어도 된다. 따라서 답은 $2$가 된다.

세 번째 예제에서는 같은 열에 서로 다른 반의 학생 두 명이 있는 경우가 없으므로 각 반에 서로 다른 색을 배정할 수 있다. 답은 $3$이다.

마지막 예제에서는 A반, B반, C반의 모든 학생에게 한 가지 색을 배정하고, D반과 E반의 모든 학생에게 다른 한 가지 색을 배정할 수 있다. 답은 $2$이다.