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