Последнее время Барни проводил с Норой и ему кажется, что у него есть к ней чувства. Барни хочет отправить ей текстовое сообщение и сделать ее как можно счастливее.
Исходно уровень счастья Норы равен 0. Нора обожает любовные строчки вроде «Я запал на тебя» и подобные. Нора знает всего n любовных строчек, каждая из которых состоит только из строчных букв латинского алфавита, а некоторые из них могут совпадать (в написании, но различаться в произношении или значении). Каждый раз, когда Нора встречает i-ю из известных ей любовных строчек как непрерывную подстроку сообщения Барни, ее уровень счастья увеличивается на ai. Эти подстроки могут пересекаться, к примеру, в тексте aaab она встретит строку aa дважды, а строку ab один раз.
В связи с ограничениями системы сообщений, текстовое сообщение Барни может содержать до l символов.
Барни просит вас помочь ему сделать Нору как можно счастливее, это будет леген...
Выходные данные
Выведите единственное целое число — максимально возможный уровень счастья Норы после прочтения текстового сообщения Барни.
Примечание
Оптимальный ответ в первом примере из условия — hearth, содержащий каждую любовную строчку ровно по одному разу.
Оптимальным ответом во втором примере из условия является строка artart.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 6
3 2 1
heart
earth
art
|
6
|
|
2
|
3 6
3 2 8
heart
earth
art
|
16
|