D. Леген...
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Последнее время Барни проводил с Норой и ему кажется, что у него есть к ней чувства. Барни хочет отправить ей текстовое сообщение и сделать ее как можно счастливее.

Исходно уровень счастья Норы равен 0. Нора обожает любовные строчки вроде «Я запал на тебя» и подобные. Нора знает всего n любовных строчек, каждая из которых состоит только из строчных букв латинского алфавита, а некоторые из них могут совпадать (в написании, но различаться в произношении или значении). Каждый раз, когда Нора встречает i-ю из известных ей любовных строчек как непрерывную подстроку сообщения Барни, ее уровень счастья увеличивается на ai. Эти подстроки могут пересекаться, к примеру, в тексте aaab она встретит строку aa дважды, а строку ab один раз.

В связи с ограничениями системы сообщений, текстовое сообщение Барни может содержать до l символов.

Барни просит вас помочь ему сделать Нору как можно счастливее, это будет леген...

Входные данные

Первая строка входных данных содержит два целых числа n и l (1 ≤ n ≤ 200, 1 ≤ l ≤ 1014) — количество любовных строчек и максимальная длина текстового сообщения Барни.

Во второй строке содержатся n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 100), означающих, что уровень счастья Норы увеличивается на ai каждый раз, когда она видит i-ую любовную строчку.

Следующие n строк содержат любовные строчки. i-ая из них содержит строку si, состоящую только из строчных букв латинского алфавита. Сумма длин любовных строчек не превышает 200.

Все строки во входных данных не пустые.

Выходные данные

Выведите единственное целое число — максимально возможный уровень счастья Норы после прочтения текстового сообщения Барни.

Примеры
Входные данные
3 6
3 2 1
heart
earth
art
Выходные данные
6
Входные данные
3 6
3 2 8
heart
earth
art
Выходные данные
16
Примечание

Оптимальный ответ в первом примере из условия — hearth, содержащий каждую любовную строчку ровно по одному разу.

Оптимальным ответом во втором примере из условия является строка artart.