题目描述

$\red{Bessie }$在玩一款游戏，该游戏只有三个技能键 $\red{A，}$$\red{B，}$$\red{C }$可用，但这些键可用形成 $\red{n }$种特定的组合技。第 $\red{i }$个组合技用一个字符串 $\red{s_i}$表示。

$\red{Bessie }$会输入一个长度为 $\red{k }$的字符串 $\red{t，}$而一个组合技每在 $\red{t }$中出现一次，$\red{Bessie }$就会获得一分。$\red{s_i }$在 $\red{t}$中出现一次指的是 $\red{s_i}$是 $\red{t }$从某个位置起的连续子串。如果 $\red{s_i}$从 $\red{t }$的多个位置起都是连续子串，那么算作 $\red{s_i }$出现了多次。

若 $\red{Bessie }$输入了恰好 $\red{k}$个字符，则她最多能获得多少分？

输入格式

输入的第一行是两个整数，分别表示组合技个数 $\red{n }$和 $\red{Bessie }$输入的字符数 $\red{k}$。

接下来 $\red{n }$行，每行一个字符串 $\red{s_i ，}$表示一种组合技。

输出格式

输出一行一个整数表示答案。

样例

输入样例

3 7 
ABA 
CB 
ABACB

输出样例

4

提示

样例解释

$\red{Bessie }$如果输入 $\red{ABACBCB，}$则 $\red{ABA }$出现了一次，$\red{ABACB }$出现了一次，$\red{CB }$出现了两次，共得到 $\red{4 }$分。可以证明这是最优的输入。

数据规模与约定

对于全部的测试点，保证：

$\red{1≤}$$\red{n≤}$$\red{20，}$$\red{1 \leq k \leq 10^3}$

$\red{1 \leq |s_i| \leq 15}$。其中 $\red{|s_i|}$表示字符串 $\red{s_i}$的长度。

$\red{s }$中只含大写字母 $\red{A，}$$\red{B，}$$\red{C}$。