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，表示一种组合技。

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

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。

USACO