C. LionAge II
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Вася играет в LionAge II. Ему надоело играть с глупым компьютером, поэтому он поставил себе эту популярнейшую MMORPG, чтобы сражаться со своими друзьями. Вася придумал имя своему персонажу — непустую строку s, состоящую из маленьких латинских букв. Однако, чтобы не ударить в грязь лицом перед друзьями, Вася решил изменить не более k букв имени персонажа таким образом, чтобы новое имя звучало как можно лучше. Благозвучие строки определяется следующим образом: для каждой пары соседних символов x и y (x находится в строке непосредственно перед y) к результату добавляется бонус c(x, y). Ваша задача определить, какое наибольшее благозвучие можно получить, изменив не более k букв в имени персонажа Васи.

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

В первой строке содержится имя персонажа s и целое число k (0 ≤ k ≤ 100). Длина непустой строки s не превосходит 100. Во второй строке находится число n (0 ≤ n ≤ 676) — количество пар символов, сочетание которых дает бонус к благозвучию. Далее следует n строк с описанием этих пар в формате «x y c», которое означает, что сочетание xy дает бонус c (x, y — маленькие латинские буквы,  - 1000 ≤ c ≤ 1000). Гарантируется, что никакая пара x y не встречается во входных данных дважды.

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

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

Примеры
Входные данные
winner 4
4
s e 7
o s 8
l o 13
o o 8
Выходные данные
36
Входные данные
abcdef 1
5
a b -10
b c 5
c d 5
d e 5
e f 5
Выходные данные
20
Примечание

В первом примере самым благозвучным именем будет looser. Не трудно посчитать, что его благозвучие составит 36.