Компліменти#2602

Компліменти

1 секунда
128 мегабайтів

Аня хоче написати Вані повідомлення, яке підніме йому настрій якомога сильніше. Ваня знає компліментів. Кожен комплімент — це непорожній рядок із малих латинських літер. Деякі компліменти можуть збігатися за написанням: це різні компліменти, які пишуться однаково.

Спочатку настрій Вані дорівнює . Щоразу, коли -й комплімент трапляється в повідомленні як неперервний підрядок, настрій Вані збільшується на a_i. Входження можуть перетинатися, і кожне з них враховується окремо. Наприклад, у повідомленні рядок трапляється двічі, а рядок — один раз.

Повідомлення може містити не більше ніж символів. Знайдіть найбільше значення, якого може досягти настрій Вані після прочитання повідомлення.

Вхідні дані

У першому рядку записано два цілих числа і l~(1 \le n \le 200, 1 \le l \le 10^{14}) — кількість компліментів і найбільша допустима довжина повідомлення.

У другому рядку записано цілих чисел a_1, a_2, \ldots, a_n~(1 \le a_i \le 100). Число a_i показує, на скільки збільшується настрій Вані при кожному входженні -го компліменту.

У кожному з наступних рядків записано один комплімент: в -му з них — непорожній рядок s_i із малих латинських літер. Сумарна довжина всіх рядків s_i не перевищує .

Вихідні дані

Виведіть одне ціле число — найбільше можливе значення настрою Вані.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Примітка

У першому прикладі підходить повідомлення : кожен комплімент трапляється в ньому рівно один раз, і настрій дорівнює 3 + 2 + 1 = 6.

У другому прикладі підходить повідомлення artart: комплімент трапляється в ньому двічі, і настрій дорівнює 8 + 8 = 16.