题目描述

农夫约翰拥有$\red{N}$头带斑点的奶牛和$\red{N}$头没有斑点的奶牛。他刚刚完成了牛遗传学课程，他确信奶牛上的斑点是由牛基因组突变引起的。

农夫约翰花了大钱对他奶牛的基因组进行测序。每个基因组都是一串长度为$\red{M}$的字符串，由四个字符$\red{A，}$$\red{C，}$$\red{G}$和$\red{T}$构成。当他排列奶牛的基因组时，他得到一张如下表，如下所示

对于$\red{N = 3}$和$\red{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

他仔细查看该表，认为从位置$\red{2}$到位置$\red{5}$的顺序足以解释斑点。也就是说，仅通过查看这些位置（即位置$\red{2 }$……$\red{5）}$中的字符，农夫约翰就可以预测出他的哪些母牛斑点，哪些不是斑点。例如，如果他在这些位置看到字符$\red{GTCG，}$他就知道那头母牛一定是斑点的。

请帮助$\red{FJ}$找到可以解释斑点的最短位置序列的长度。

$\red{FJ}$有一些有斑点和一些没有斑点的牛，他想搞清楚到底什么基因控制这个牛有没有斑点。

于是他找了$\red{n}$有斑点的牛和$\red{n}$头没有斑点的牛

这些牛的基因长度为$\red{m（}$基因中之包含$\red{ATCG}$四个字母）

求这个序列中的一个子串，可以确定是否有斑点。

子串需要符合要求：有斑点的牛这部分的子串，不能和无斑点的牛的这部分子串相同

求最短子串长度

输入格式

输入的第一行包含$\red{N (1 \leq N \leq 500）}$ 和$\red{M(3 \leq M \leq 500）}$。下一个$\red{N}$每行包含一串$\red{M}$人物; 这些描述了斑点奶牛的基因组。

决赛$\red{N}$线条描述了普通奶牛的基因组。没有斑点奶牛与普通奶牛具有相同的基因组。

输出格式

请打印足以解释斑点的最短位置序列的长度。如果仅通过查看基因组中的这些位置，就可以在 $\red{Farmer John }$的奶牛群中完全准确地预测斑点性状，那么一系列位置就可以解释斑点性状。

样例

输入样例

3 8
AATCCCAT
ACTTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

输出样例

4