Последнее время Барни проводил с Норой и ему кажется, что у него есть к ней чувства. Барни хочет отправить ей текстовое сообщение и сделать ее как можно счастливее.
Исходно уровень счастья Норы равен 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.
| Codeforces Round 362 (Div. 1) |
|---|
| Закончено |
