Spottiness Explanation

Farmer John owns \(N\) cows with spots and \(N\) cows without spots. After learning about bovine genetics, he believes that mutations in the bovine genome cause spottiness. He sequences the genomes of his cows; each genome is a string of length \(M\) built from the characters A, C, G, and T.

When he lines up the genomes, he obtains a table. For example, for \(N = 3\) and \(M = 8\):

Positions:      1 2 3 4 5 6 7 8
Spotty Cow 1:   A A T C C C A T
Spotty Cow 2:   A C T T G C A A
Spotty Cow 3:   G G T C G C A A
Plain Cow 1:    A C T C C C A G
Plain Cow 2:    A C T C G C A T
Plain Cow 3:    A C T T C C A T

Farmer John observed that the contiguous sequence from positions \(i\) to \(j\) might be sufficient to explain spottiness; that is, by only looking at the characters in these positions (a substring of length \(L = j-i+1\)), he can differentiate spotty cows from plain cows. For instance, the sequence from positions 2 to 5 in the example above can be used to uniquely identify spotty cows.

Your task is to help Farmer John find the minimum length \(L\) of a contiguous sequence of positions that can explain spottiness. In other words, choose indices \(i\) and \(j\) (with \(1 \le i \le j \le M\)) such that the set of substrings (from position \(i\) to \(j\)) for the spotty cows and the set for the plain cows do not intersect, and \(L = j-i+1\) is minimized.

Input and Output formats are given below.

inputFormat

The first line contains two integers (N) and (M) ((1 \leq N, M \leq 500) for example) -- the number of spotty cows (and plain cows) and the length of each genome. The next (N) lines each contain a string of length (M) representing the genome of a spotty cow. The following (N) lines each contain a string of length (M) representing the genome of a plain cow.

outputFormat

Output a single integer: the minimum length (L = j-i+1) of a contiguous substring of positions that can distinguish all spotty cows from all plain cows.

sample

3 8
AATCCCAT
ACTTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

4