← 返回题目列表

Codeforces · 696/D

D. 传说...

中文机器翻译题面 查看原题

巴尼和诺拉出去玩了一段时间,现在他认为自己可能对她有感觉。巴尼想给她发一条俗气的短信,想让她尽可能开心。

最初,Nora 的幸福度为 0。Nora 喜欢一些搭讪台词,比如“我爱上你了”之类的。她总共知道 n 条搭讪台词,每条台词仅由小写英文字母组成,而且其中一些可能是相同的(书面形式,但发音或含义不同)。每当诺拉看到第 i 个搭讪台词是巴尼短信的连续子序列时,她的幸福感就会增加 ai。这些子串可能会重叠,例如,Nora 在文本消息 aaab 中会看到两次代答线路 aa 和一次代答线路 ab。

由于短信应用的限制,Barney 的文本最多可能有 l 个字符。

巴尼请你帮助他尽可能让诺拉快乐,这将会成为传奇......

输入

输入的第一行包含两个整数 n 和 l (1 ≤ n ≤ 200, 1 ≤ l ≤ 1014) - 拾取行数和 Barney 文本的最大长度。

第二行包含n个整数a1, a2, ..., an (1 ≤ ai ≤ 100),这意味着Nora的幸福感在每次看到第i条搭接线后增加ai。

接下来的 n 行包含代答行。其中第 i 个包含仅由英文小写字母组成的单个字符串 si。所有拾取行的汇总长度不超过 200。

所有字符串都不为空。

输出

打印唯一的整数——读完巴尼的文本后诺拉幸福水平的最大可能值。

示例

输入 #1

3 6
3 2 1
heart
earth
art

输出 #1

6

输入 #2

3 6
3 2 8
heart
earth
art

输出 #2

16

注意

第一个示例案例的最佳答案是每条拾取线仅包含一次的炉床。

第二个示例案例的最佳答案是 artart。