题目描述

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

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

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

输入格式

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

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

输出格式

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

样例

输入样例

3 7 
ABA 
CB 
ABACB

输出样例

4

提示

样例解释

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

数据规模与约定

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

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

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

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