OneDay的短信

发布时间: 2018年1月21日 17:53   最后更新: 2018年1月29日 10:30   时间限制: 10000ms   内存限制: 256M

OneDay和qhl混了一阵子,现在他觉得他可能对她有感情。现在OneDay想给她发一条短信,并让她尽可能高兴。

起初,qhl的高兴值为0。已知qhl听到一些词语的时候会比较高兴。具体地,有$n$个单词,每个单词都只有小写字母组成,可能有相同的单词(书写相同,意义不同)。每当qhl阅读到的短信含有第$i$个单词,她的高兴值就会增加$a_i$。

注意:子串可以重叠,比如当qhl看到"aaab"的时候,她将得到两次"aa"的高兴值。

OneDay比较穷,他只能发送长度为$l$的短信,他又想让qhl尽可能高兴。

有多组测试数据(不超过20组),每组数据的第一行为两个整数$n,l$
第二行为$n$个整数$a_1,a_2,...a_n$
接下来$n$行,每行有一个非空字符串,仅由小写字母组成。
$1\le n \le 200$
$1\le l \le 10^{14}$
$1\le a_i \le 100$
$\sum |s_i| \le 200$

对于每组测试数据,输出一个整数,表示qhl能得到的最大高兴值

复制
3 6
3 2 1
abcde
bcdef
cde
3 6
3 2 8
abcde
bcdef
cde
6
16

第一组样例:abcdef

第二组样例:cdecde

dp data structure string

Weekly Training 2018.1.21