CF73C.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.

瓦西娅正在玩《狮龄II》。他厌倦了与愚蠢的电脑对战，于是安装了这款热门大型多人在线角色扮演游戏（MMORPG），以便与朋友们一起战斗。瓦西娅为自己的角色想出了一个名字——一个非空字符串 $s$，由小写拉丁字母组成。然而，为了不在朋友面前丢面子，瓦西娅决定最多修改字符名中的 $k$ 个字母，使得新名字听起来尽可能悦耳。字符串的“悦耳度”定义如下：对每一对相邻字母 $x$ 和 $y$（即 $x$ 紧邻在 $y$ 之前），向总悦耳度中加上奖励值 $c(x,\,y)$。你的任务是：通过最多修改 $k$ 个字母，求出瓦西娅角色名所能达到的最大悦耳度。

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.

第一行包含角色名称 $s$ 和一个整数 $k$（$0 \leq k \leq 100$）。非空字符串 $s$ 的长度不超过 $100$。
第二行包含一个整数 $n$（$0 \leq n \leq 676$）—— 表示能为音韵度提供加成的字母对的数量。
接下来的 $n$ 行描述这些字母对，格式为 «$x$ $y$ $c$»，表示子序列 $xy$ 提供加成 $c$（其中 $x$、$y$ 为小写拉丁字母，$-1000 \leq c \leq 1000$）。
保证输入数据中任意一对 $x$ $y$ 不会重复出现。

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

输出唯一的数字——新角色名字可能达到的最大悦耳度。

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

在第一个例子中，最悦耳的名字是 looser。很容易计算出它的悦耳度为 36。