G. Падение
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы упали в какую-то дыру и после нескольких часов беспамятства обнаружили себя в подземном городе. Во время одной из ежедневных прогулок в неизвестность вы встретили двух забавных скетелов Санца и Ппариуса, который почему то решили составить вам компанию и выдали вам несколько загадок.

В один из дней, Санц сделал для вас кроссворд. Да не просто кроссворд, а 1D кроссворд! Вам дано m слов и строка длины n. Также дан массив p, который для каждого слова определяет его стоимость — i-е слово стоит pi очков. Как только вы встречаете в строке одно из m слов, вы получаете соответствующее количество очков. Каждая позиция в строке может быть использована не более чем x раз. Различные вхождения одного и того же слова могут быть учтены несколько раз, но не более чем один раз на каждое вхождение. Если слово является подстрокой другого слова, то есть можно учитывать несколько раз (при условии выполнения требования на использование позиций не более чем x раз).

Чтобы решить данный пазл, требуется сказать Санцу максимально возможный счёт, который можно набрать. Нет необходимости покрывать все позиции, главное максимизировать свой счёт. Кроссворд и слова состоят только из строчных букв английского алфавита.

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

В первой строке входных данных записано целое число n (1 ≤ n ≤ 500) — длина кроссворда. Во второй строке записана строка кроссворда. В третьей строке находится целое число m (1 ≤ m ≤ 100) — количество слов. Далее следуют m описаний слов, каждое из них состоит из строки, обозначающей данное слово, и числа pi (0 ≤ pi ≤ 100). В последней строке записано целое число x (1 ≤ x ≤ 100) — максимальное количество раз, которое разрешается использовать одну позицию кроссворда.

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

Выведите одно целое число — максимальное количество очков, которое можно получить.

Пример
Входные данные
6
abacba
2
aba 6
ba 3
3
Выходные данные
12
Примечание

Например, для строки «abacba», слов «aba» (6 очков) и «ba» (3 очка), и x = 3, мы можем заработать 12 очков — слово «aba» встречается один раз, а слово «ba» дважды. Обратите внимание, что для x = 1 можно получить не более 9 очков, поскольку нельзя одновременно взять «aba» и первое вхождение «ba».