Задача L. Пожиратель строк

Автор:Артём Завгороднев   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

В мире монстра Василия вся пища представляет из себя строки, которые состоят из символов. У каждого символа есть свое целое число - сытность. А сытностью строки называется сумма сытностей её символов.

Сегодня у монстра на обед строка s длины n.

Василий достаточно странное существо, поэтому в еде у него есть несколько правил:

Василий просит вас найти строку с максимальной сытность, которую он бы мог съесть.

Формат входных данных

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

В следующих М строках располагаются символ si и целое число ai - его сытость (1 ≤ ai ≤ 100).

В следующей строке два целых числа n и k (1 ≤ k ≤ n ≤ 106) - длина строки и размер живота Василия.

В последней строке строка s длины n.

Формат выходных данных

Вам необходимо вывести одно целое число - сытность найденной строки.

Примеры тестов

Стандартный вход Стандартный выход
1
5
a 1
b 2
c 3
d 4
1 5
10 3
abcdbdab1c
10
2
1
1 10
5 5
11111
10

0.091s 0.017s 15