给定 $n$ 个字符串，每个字符串都是前 $k$ 个大写字母的一个排列。

如果字符串 $s$ 可以通过从字符串 $t$ 中删除若干（可能为零）个字符得到，则称 $s$ 是 $t$ 的子序列。

计算这 $n$ 个字符串的最长公共子序列的长度。

输入的第一行包含两个整数 $n$ ($1 \le n \le 10^5$) 和 $k$ ($1 \le k \le 26$)，其中 $n$ 是字符串的数量，所有字符串均为前 $k$ 个大写字母的排列。

接下来的 $n$ 行，每行包含一个字符串 $t$。保证每个 $t$ 都恰好包含前 $k$ 个大写字母中的每一个字符各一次。

输出一个整数，表示在所有 $n$ 个字符串中出现的最长公共子序列的长度。

样例

输入格式 1

2 3
BAC
ABC

输出格式 1

2

输入格式 2

3 8
HGBDFCAE
ADBGHFCE
HCFGBDAE

输出格式 2

3

输入格式 3

6 8
AHFBGDCE
FABGCEHD
AHDGFBCE
DABHGCFE
ABCHFEDG
DGABHFCE

输出格式 3

4