题目描述

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

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

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

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

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

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

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

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

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

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

求最短子串长度

输入格式

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

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

输出格式

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

样例

输入样例

3 8
AATCCCAT
ACTTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

输出样例

4