A8139 | LionAge II

Vasya plays the LionAge II. He was bored of playing with a stupid computer, so he installed this popular MMORPG, to fight with his friends. Vasya came up with the name of his character — non-empty string $s$ , consisting of a lowercase Latin letters. However, in order not to put up a front of friends, Vasya has decided to change no more than $k$ letters of the character name so that the new name sounded as good as possible. Euphony of the line is defined as follows: for each pair of adjacent letters $x$ and $y$ ( $x$ immediately precedes $y$ ) the bonus $c(x,y)$ is added to the result. Your task is to determine what the greatest Euphony can be obtained by changing at most $k$ letters in the name of the Vasya's character.

The first line contains character's name $s$ and an integer number $k$ ( $0<=k<=100$ ). The length of the nonempty string $s$ does not exceed $100$ . The second line contains an integer number $n$ ( $0<=n<=676$ ) — amount of pairs of letters, giving bonus to the euphony. The next $n$ lines contain description of these pairs « $x$ $y$ $c$ », which means that sequence $xy$ gives bonus $c$ ( $x,y$ — lowercase Latin letters, $-1000<=c<=1000)$ . It is guaranteed that no pair $x$ $y$ mentioned twice in the input data.

Output the only number — maximum possible euphony оf the new character's name.