Вася играет в 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 не встречается во входных данных дважды.
Вывести единственное число — максимально возможное благозвучие нового имени персонажа.
В первом примере самым благозвучным именем будет looser. Не трудно посчитать, что его благозвучие составит 36.
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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач