Вы упали в какую-то дыру и после нескольких часов беспамятства обнаружили себя в подземном городе. Во время одной из ежедневных прогулок в неизвестность вы встретили двух забавных скетелов Санца и Ппариуса, который почему то решили составить вам компанию и выдали вам несколько загадок.
В один из дней, Санц сделал для вас кроссворд. Да не просто кроссворд, а 1D кроссворд! Вам дано m слов и строка длины n. Также дан массив p, который для каждого слова определяет его стоимость — i-е слово стоит pi очков. Как только вы встречаете в строке одно из m слов, вы получаете соответствующее количество очков. Каждая позиция в строке может быть использована не более чем x раз. Различные вхождения одного и того же слова могут быть учтены несколько раз, но не более чем один раз на каждое вхождение. Если слово является подстрокой другого слова, то есть можно учитывать несколько раз (при условии выполнения требования на использование позиций не более чем x раз).
Чтобы решить данный пазл, требуется сказать Санцу максимально возможный счёт, который можно набрать. Нет необходимости покрывать все позиции, главное максимизировать свой счёт. Кроссворд и слова состоят только из строчных букв английского алфавита.
Выходные данные
Выведите одно целое число — максимальное количество очков, которое можно получить.
Примечание
Например, для строки «abacba», слов «aba» (6 очков) и «ba» (3 очка), и x = 3, мы можем заработать 12 очков — слово «aba» встречается один раз, а слово «ba» дважды. Обратите внимание, что для x = 1 можно получить не более 9 очков, поскольку нельзя одновременно взять «aba» и первое вхождение «ba».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
abacba
2
aba 6
ba 3
3
|
12
|