문제

충남대학교 생명과학과에 재학 중인 현석이는 유전학 수업을 마치고 학생들의 게놈(Genome)을 분석하여 특정 형질이 나타나는 원인을 연구하고 있다. 현석이는 특정 형질을 가진 학생 $N$명과 해당 형질이 없는 학생 $N$명의 게놈 데이터를 수집했다.

각 게놈은 A, C, G, T 네 종류의 문자로 구성된 길이 $M$의 문자열이다. 예를 들어, $N=3, M=8$일 때의 데이터는 다음과 같다.

위치:         1 2 3 4 5 6 7 8

형질이 있는 학생 1: A A T C C C A T
형질이 있는 학생 2: A C T T G C A A
형질이 있는 학생 3: G G T C G C A A

형질이 없는 학생 1: A C T C C C A G
형질이 없는 학생 2: A C T C G C A T
형질이 없는 학생 3: A C T T C C A T

현석이는 이 표를 정밀하게 분석한 결과, $2$번 위치부터 $5$번 위치까지의 연속된 구간이 형질의 유무를 설명하기에 충분하다는 가설을 세웠다. 즉, 이 구간($2 \ldots 5$)의 문자들만 보고도 해당 학생이 어느 그룹에 속하는지 완벽하게 예측할 수 있다는 것이다. 예를 들어, 해당 위치에서 GTCG라는 서열이 발견된다면, 현석이는 그 학생이 반드시 형질을 가진 그룹에 속한다는 것을 알 수 있다.

현석이를 도와 형질의 유무를 완벽하게 판별할 수 있는 가장 짧은 연속된 구간의 길이를 구하시오.

입력

첫째 줄에 학생 수 $N$과 게놈의 길이 $M$이 공백으로 구분되어 주어진다. ($1 \le N \le 500$; $3 \le M \le 500$)

이어서 $N$개의 줄에 형질이 있는 학생들의 게놈이 각각 길이 $M$인 문자열로 주어진다.

마지막 $N$개의 줄에는 형질이 없는 학생들의 게놈이 각각 길이 $M$인 문자열로 주어진다.

형질이 있는 학생의 전체 게놈 서열이 형질이 없는 학생의 전체 게놈 서열과 완전히 일치하는 경우는 없다.

출력

두 그룹을 완벽하게 구분할 수 있는 가장 짧은 연속된 구간의 길이를 출력한다. 특정 구간의 서열들만 보았을 때, 형질이 있는 학생 그룹에서 나타나는 서열이 형질이 없는 학생 그룹에서 단 한 번도 나타나지 않는다면 그 구간은 두 그룹을 완벽하게 구분할 수 있다고 한다.

예제 입력 1

3 8
AATCCCAT
ACTTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

예제 출력 1

4