#Paho16. 1.组合攻击

1.组合攻击

1.组合攻击

题目描述

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

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

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

输入格式

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

接下来n行,每行一个字符串sis_i​,表示一种组合技。

输出格式

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

数据范围

(原站未提供,导入后需人工补齐)

样例

3 7 
ABA 
CB 
ABACB 
4 

提示

样例解释

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

对于全部的测试点,保证:

1<=n<=20,1<=k<=1031<=n<=20,1<=k<=10^3。

1<=∣Si∣<=15。其中∣Si∣表示字符串​Si1<=|S_i|<=15。其中|S_i|表示字符串​S_i的长度。

s中只含大写字母A,B,C。