CF73C LionAge II

瓦西亚正在玩 LionAge II。厌倦了与“愚蠢的计算机”对战，他安装了热门的 MMORPG，与朋友一起战斗。瓦西亚为自己的角色想了一个名字 —— 一个由小写拉丁字母组成的非空字符串 $s$。但为了不在朋友面前“装样子”，他决定将角色名中不超过 $k$ 个字母修改为其它字母，使新的名字尽可能“悦耳”。一串字符串的“悦耳度”定义如下：对于每一对相邻字母 $x$ 和 $y$（$x$ 紧邻在 $y$ 之前），会向总分中加上 $c(x,y)$ 的奖励。你的任务是计算，最多允许修改 $k$ 个字母后，瓦西亚的角色名称最多能获得多少“悦耳度”。

第一行包含角色名称 $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$ 对。

输出一个整数，表示经过最多 $k$ 次修改后能获得的最大“悦耳度”。

在第一个样例中，最“悦耳”的角色名将会是 $looser$。容易计算其“悦耳度”为 $36$。 由 ChatGPT 5 翻译