모자이크 맨션

시간 제한12초메모리 제한512 MB

요약

n개의 행과 m개의 열로 이루어진 모자이크가 주어질 때, 남긴 행들에서 각 색의 타일 수가 모두 같아지도록 행을 제거하고, 남길 수 있는 행의 최대 개수를 구한다.

문제

모자이크는 정사각형 타일을 격자에 배열해 만든 그림이다. 적어도 오늘 다룰 문제에서는 그렇다.

우리는 각 색깔의 타일 개수가 정확히 같도록 모자이크를 만들고자 한다. 기존 디자인에서 일부 행을 제거하는 방식으로 이를 달성한다.

그림 M.1: 예제 입력 1에 대한 해답의 예시. 흰색으로 표시된 세 개의 행을 남기면 각 색깔의 타일을 6개씩 얻을 수 있다.

남길 수 있는 행의 최대 개수는 얼마인가?

첫째 줄에 모자이크의 행 개수 n (1 ≤ n ≤ 40), 열 개수 m (1 ≤ m ≤ 105), 색깔 개수 c (1 ≤ c ≤ 105)이 주어진다.
다음 n개의 줄 각각에는 m개의 셀 색깔 p1 . . . pm (1 ≤ p ≤ c)이 주어진다.

입력에서 각 색깔이 동일한 비율로 나타나도록 유지하면서 남길 수 있는 행의 최대 개수를 출력한다. 남길 수 있는 행이 없으면 0을 출력한다.

예제 1

입력

4 10 5
1 2 1 2 3 1 2 3 4 3
5 2 5 3 5 5 5 5 1 4
2 3 2 1 4 3 3 2 1 4
1 2 3 4 4 4 4 1 2 3

예상 출력