Олимпиадный тренинг

Задача 27218. Bovine Genomics


Задача

Темы:
Farmer John has NN spotted cows and NN spotless cows. After taking a course in genetics, the FD is convinced that the spots in cows are caused by a gene mutation.
For a lot of money, FD fixed the genomes of his cows. Each genome is a string of length MM, consisting of the characters A, C, G, T. When he wrote out all the genomes, he got the following table, N=3 and M=8:
 
Position  :                   1 2 3 4 5 6 7 8
 
Spotted Cow 1:  A A T C C C A T
Spotted Cow 2:  A C T T G C A A
Spotted Cow 3:  G G T C G C A A
 
Spotless cow 1:  A C T C C C A G
Spotless Cow 2:  A C T C G C A T
Spotless cow 3:  A C T T C C A T

Looking closely at this table, he noticed that the sequence from position 2 to position 5 was successful in explaining the spotting. That is, by looking at the characters at these positions (2*5), the FD can predict which of his cows are spotted and which are not. For example, if he sees the GTCG characters in these positions, he knows that the cow will be spotted.
 
Help the FD determine the length of the shortest sequence of positions that can explain the spotting.
 
INPUT FORMAT:
 
The first input line contains N (1≤N≤500) and M (3≤M≤500). Each of the next N lines contains M characters. These symbols describe the genomes of spotted cows. The next N lines describe the genomes of cows without spots. No spotted cow has exactly the same genome as a non-spotted cow.
 
OUTPUT FORMAT:
 
Please print the length of the shortest sequence of positions sufficient to explain the spotting. The sequence of positions explains spotting if it can be used to predict exactly whether or not any of the FD cows is spotted.

Enter Output
38
AATCCCAT
ACTTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT
4