Anya wants to write Vanya a message that will lift his mood as much as possible. Vanya knows compliments. Each compliment is a nonempty string of lowercase Latin letters. Some compliments may be spelled the same way: they are different compliments that happen to be written identically.
Initially, Vanya's mood is . Each time the -th compliment occurs in the message as a contiguous substring, Vanya's mood increases by a_i. Occurrences may overlap, and each of them is counted separately. For example, in the message the string occurs twice, and the string occurs once.
The message may contain at most characters. Find the maximum value that Vanya's mood can reach after reading the message.
The first line contains two integers and l~(1 \le n \le 200, 1 \le l \le 10^{14}) — the number of compliments and the maximum allowed length of the message.
The second line contains integers a_1, a_2, \ldots, a_n~(1 \le a_i \le 100). The number a_i is the amount by which Vanya's mood increases with each occurrence of the -th compliment.
Each of the next lines contains one compliment: the -th of them contains a nonempty string s_i of lowercase Latin letters. The total length of all strings s_i does not exceed .
Print one integer — the maximum possible value of Vanya's mood.
Example 1
Example 2
In the first example, the message works: each compliment occurs in it exactly once, and the mood equals 3 + 2 + 1 = 6.
In the second example, the message artart works: the compliment occurs in it twice, and the mood equals 8 + 8 = 16.