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

Условие

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

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

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

• Живот Василия не резиновый, поэтому съесть он может строку, длинной не более чем k символов.
• Он начинает есть только один раз, и только подряд идущие символы.
• Василий очень привередлив и не будет есть два одинаковых подряд идущих символа. То есть если он съел символ и далее увидел следующий такой же символ, он сразу же прекращает есть.

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

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

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

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

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

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

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

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

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

5
a 1
b 2
c 3
d 4
1 5
10 3
abcdbdab1c

10

1
1 10
5 5
11111

10