当前没有测试数据。

1.组合攻击

题目描述

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

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

若小明输入了恰好$k$个字符，则他最多能获得多少分？

输入格式

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

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

输出格式

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

数据范围与提示

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

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

样例

3 7 
ABA 
CB 
ABACB 

4

说明

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