CF696D.Legen...

Barney was hanging out with Nora for a while and now he thinks he may have feelings for her. Barney wants to send her a cheesy text message and wants to make her as happy as possible.

Initially, happiness level of Nora is 0. Nora loves some pickup lines like "I'm falling for you" and stuff. Totally, she knows n pickup lines, each consisting only of lowercase English letters, also some of them may be equal (in writing, but different in pronouncing or meaning though). Every time Nora sees i-th pickup line as a consecutive subsequence of Barney's text message her happiness level increases by a__i. These substrings may overlap, for example, Nora will see the pickup line aa twice and the pickup line ab once in text message aaab.

Due to texting app limits, Barney's text may have up to l characters.

Barney asked you to help him make Nora as much happy as possible, it's gonna be legen...

巴尼和诺拉一起待了一段时间，现在他觉得自己可能对她有好感。巴尼想给诺拉发一条肉麻的短信，并希望让她尽可能开心。

最初，诺拉的幸福值为 0。诺拉很喜欢一些搭讪语句，例如 “I'm falling for you” 之类的。她总共知道 $n$ 条搭讪语句，每条均由小写英文字母组成；其中某些语句在书写上可能完全相同（但发音或含义不同）。

每当诺拉在巴尼的短信中看到第 $i$ 条搭讪语句作为一个连续子串出现时，她的幸福值就会增加 $a_i$。这些子串可以重叠；例如，在短信 aaab 中，搭讪语句 aa 会出现两次，而 ab 会出现一次。

由于短信应用的限制，巴尼的短信最多只能包含 $l$ 个字符。

巴尼请你帮他设计一条短信，使得诺拉的幸福值尽可能高——这将是一段传奇……

The first line of input contains two integers n and l (1 ≤ n ≤ 200, 1 ≤ l ≤ 1014) — the number of pickup lines and the maximum length of Barney's text.

The second line contains n integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 100), meaning that Nora's happiness level increases by a__i after every time seeing i-th pickup line.

The next n lines contain the pickup lines. i-th of them contains a single string s__i consisting of only English lowercase letter. Summary length of all pickup lines does not exceed 200.

All strings are not empty.

输入的第一行包含两个整数 $n$ 和 $l$（$1 \leq n \leq 200$，$1 \leq l \leq 10^{14}$）——分别表示搭讪语句的数量以及 Barney 文本的最大长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 100$），表示 Nora 每次看到第 $i$ 条搭讪语句时，其幸福感增加 $a_i$。

接下来的 $n$ 行为搭讪语句。其中第 $i$ 行包含一个仅由小写英文字母组成的字符串 $s_i$。所有搭讪语句的总长度不超过 $200$。

所有字符串均非空。

Print the only integer — the maximum possible value of Nora's happiness level after reading Barney's text.

输出唯一的整数——Nora 阅读 Barney 的文本后所能达到的最大幸福值。

An optimal answer for the first sample case is hearth containing each pickup line exactly once.

An optimal answer for the second sample case is artart.

第一个样例的最优答案是包含每条搭讪语恰好一次的字符串 hearth。

第二个样例的最优答案是字符串 artart。