[USACO12JAN] Video Game G

题目描述

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

输出格式


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

输入输出样例

输入样例 #1

3 7 
ABA 
CB 
ABACB 

输出样例 #1

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`。