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.

Input

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

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

Note

In the first example the most euphony name will be $*looser*$. It is easy to calculate that its euphony is 36.