Covel（现改名为 Epicuria）的音乐播放列表提供了让学生们欲罢不能的器乐曲目。这些歌曲由 $N$ 个钢琴音符（A-G）组成，且总是非常动听。因此，学生们决定使用 Shazam 应用程序来找出要添加到他们播放列表中的歌曲，但似乎有一个问题：该应用程序永远无法识别出这是什么歌。

Covel 令人垂涎的美食

你在当前正在播放的歌曲的某个音符处启动 Shazam，此时该应用程序会听取 $K$ 个音符，并在其数据库中搜索匹配项（即数据库中包含相同 $K$ 个音符序列作为其子串的歌曲）。如果在 Shazam 听完 $K$ 个音符之前就已经到达了歌曲的末尾，它将转而只匹配数据库中以它所听到的相同序列结尾的歌曲。Shazam 必须总是至少听取一个音符（即 $K$ 必须是一个正整数）。

Shazam 的数据库中肯定包含当前正在播放的歌曲，但如果数据库中还有其他歌曲也匹配所听到的序列，它将无法唯一识别出这首歌。虽然每次都听到歌曲结束会很好，但 Shazam 受到其资源的限制，并且希望找到一个最优的 $K$ 值，因为用户可能会从歌曲的任意音符处开始听。给定当前正在播放的歌曲以及 Shazam 的歌曲数据库，求出最小的 $K$ 值，使得至少有 50% 的起始位置能够让 Shazam 成功识别出这首歌。

输入格式

输入的第一行包含两个空格分隔的整数 $N$ 和 $M$。它们分别表示每首歌的长度（$1 \le N \le 1\,000$）和数据库中的歌曲数量（$1 \le M \le 1\,000$）。

接下来的 $M$ 行表示数据库中的歌曲。每行是一个由 $N$ 个字符（A - G）组成的字符串，表示歌曲的音符。这 $M$ 行中的第一行是当前正在播放的歌曲。保证没有两首歌是完全相同的。

输出格式

输出一行，包含最小可能的 $K$ 值，使得当前播放歌曲的至少 50% 的起始位置能让 Shazam 找到唯一匹配；如果不存在这样的 $K$，则输出 $-1$。

样例

输入样例 1

4 3
ABAB
AAAA
BBBB

输出样例 1

2

输入样例 2

4 3
AAAA
AAAB
BAAA

输出样例 2

-1

说明

在第一个样例中，如果 Shazam 只听两个音符，它可以从第 1、第 2 或第 3 个音符开始，以检测到唯一的音符组合，但不能从第 4 个位置开始（因为那样第三首歌也会匹配）。这在 4 个起始音符中提供了 3 个有效的起始位置，大于 50%。

在第二个样例中，即使 Shazam 听完所有 4 个音符，也只有一个起始音符能让 Shazam 识别出这首歌，即从第一个音符开始并听取 AAAA。从第二、第三或第四个音符开始会导致 Shazam 分别听到 AAA*、AA* 和 A*，其中 * 表示歌曲的结尾。所有这些也与数据库中的第三首歌（BAAA）相匹配，因此其他起始位置都无法提供唯一匹配。