← 返回题目列表

Codeforces · 73/C

C. 狮时代 II

中文机器翻译题面 查看原题

Vasya 玩的是 LionAge II。他厌倦了玩愚蠢的电脑,所以他安装了这个流行的MMORPG,来和他的朋友们一起战斗。瓦夏想出了他的角色的名字——非空字符串 s,由小写拉丁字母组成。不过,为了不给朋友们留下印象,瓦夏决定更改角色名字中不超过k个字母,以便新名字听起来尽可能好听。该行的悦耳音定义如下:对于每对相邻字母 x 和 y(x 紧接在 y 之前),将奖励 c(x, y) 添加到结果中。你的任务是确定通过改变 Vasya 角色名字中的最多 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 被提及两次。

输出

输出新角色名字的唯一数字——最大可能的谐音。

示例

输入 #1

winner 4
4
s e 7
o s 8
l o 13
o o 8

输出 #1

36

输入 #2

abcdef 1
5
a b -10
b c 5
c d 5
d e 5
e f 5

输出 #2

20

注意

在第一个示例中,最悦耳的名称会更宽松。很容易算出它的谐音是36。