题目描述

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 

提示

样例 1 解释

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

数据规模与约定

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

• $1 \leq n \leq 20$，$1 \leq k \leq 10^3$。
• $1 \leq |s_i| \leq 15$。其中 $|s_i|$ 表示字符串 $s_i$ 的长度。
• $s$ 中只含大写字母 A，B，C。