USACO 奶牛基因组学

题目描述

农夫约翰拥有 $N$ 头有斑点的奶牛和 $N$ 头没有斑点的奶牛。在完成了一门牛遗传学课程后，他确信他奶牛身上的斑点是由牛基因组中的突变引起的。

农夫约翰花费巨资对他的奶牛进行了基因组测序。每个基因组是一个长度为 $M$ 的字符串，由四个字符 A、C、G 和 T 组成。当他将奶牛的基因组排列在一起时，他得到了如下表格（此处以 $N=3$ 和 $M=8$ 为例）：

仔细观察这个表格，他推测从位置 2 到位置 5 的序列足以解释斑点的形成。也就是说，通过观察这些位置（即位置 $2 \ldots 5$）的字符，农夫约翰可以预测他的哪些奶牛有斑点，哪些没有。例如，如果他在这些位置看到字符 GTCG，他就知道这头奶牛一定有斑点。

请帮助农夫约翰找到能够解释斑点形成的最短位置序列的长度。

输入格式

输入文件 cownomics.in 的第一行包含两个整数 $N$（$1 \leq N \leq 500$）和 $M$（$3 \leq M \leq 500$）。

接下来的 $N$ 行每行包含一个长度为 $M$ 的字符串，描述斑点牛的基因组。

最后的 $N$ 行每行包含一个长度为 $M$ 的字符串，描述无斑点牛的基因组。

没有斑点牛与无斑点牛具有完全相同的基因组。

输出格式

输出文件 cownomics.out 应包含一个整数，表示能够解释斑点形成的最短位置序列的长度。如果一个位置序列能够通过观察基因组中的这些位置来完美预测农夫约翰牛群中的斑点性状，则该位置序列足以解释斑点形成。

样例输入

3 8
AATCCCAT
ACTTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

样例输出

4

样例解释

观察位置 2 到 5（即第 2、3、4、5 个字符）的序列足以区分斑点牛和无斑点牛。例如，在这些位置：

• 斑点牛 1 的序列是：A T C C
• 斑点牛 2 的序列是：C T T G
• 斑点牛 3 的序列是：G T C G
• 无斑点牛 1 的序列是：C T C C
• 无斑点牛 2 的序列是：C T C G
• 无斑点牛 3 的序列是：C T T C

任意一个斑点牛的 4 字符序列都不会出现在任何无斑点牛中，反之亦然。

数据范围

• $1 \leq N \leq 500$
• $3 \leq M \leq 500$