{"raw_statement":[{"iden":"statement","content":"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."},{"iden":"input","content":"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."},{"iden":"output","content":"Output the only number — maximum possible euphony оf the new character's name."},{"iden":"examples","content":"Input\n\nwinner 4\n4\ns e 7\no s 8\nl o 13\no o 8\n\nOutput\n\n36\n\nInput\n\nabcdef 1\n5\na b -10\nb c 5\nc d 5\nd e 5\ne f 5\n\nOutput\n\n20"},{"iden":"note","content":"In the first example the most euphony name will be _looser_. It is easy to calculate that its euphony is 36."}],"translated_statement":[{"iden":"statement","content":"Vasya 正在玩《LionAge II》。他厌倦了和愚蠢的电脑对战，于是安装了这款流行的 MMORPG，以便与朋友对战。Vasya 为他的角色想了一个名字——一个由小写拉丁字母组成的非空字符串 #cf_span[s]。然而，为了避免在朋友面前出风头，Vasya 决定最多修改 #cf_span[k] 个字母，使新名字听起来尽可能悦耳。一个字符串的悦耳度定义如下：对于每一对相邻字母 #cf_span[x] 和 #cf_span[y]（#cf_span[x] 紧邻在 #cf_span[y] 之前），将加上奖励值 #cf_span[c(x, y)]。你的任务是确定，在最多修改 #cf_span[k] 个字母的前提下，Vasya 角色名字所能获得的最大悦耳度。\n\n第一行包含角色的名字 #cf_span[s] 和一个整数 #cf_span[k]（#cf_span[0 ≤ k ≤ 100]）。非空字符串 #cf_span[s] 的长度不超过 #cf_span[100]。第二行包含一个整数 #cf_span[n]（#cf_span[0 ≤ n ≤ 676]）——能带来悦耳度奖励的字母对数量。接下来的 #cf_span[n] 行每行描述一个这样的字母对 «#cf_span[x] #cf_span[y] #cf_span[c]»，表示序列 #cf_span[xy] 会带来奖励 #cf_span[c]（#cf_span[x, y] 为小写拉丁字母，#cf_span[ - 1000 ≤ c ≤ 1000]）。保证输入数据中不会出现重复的字母对 #cf_span[x] #cf_span[y]。\n\n输出一个数字——新角色名字可能达到的最大悦耳度。\n\n在第一个例子中，最悦耳的名字将是 #cf_span[looser]。可以轻松计算出其悦耳度为 36。\n\n"},{"iden":"input","content":"第一行包含角色的名字 #cf_span[s] 和一个整数 #cf_span[k]（#cf_span[0 ≤ k ≤ 100]）。非空字符串 #cf_span[s] 的长度不超过 #cf_span[100]。第二行包含一个整数 #cf_span[n]（#cf_span[0 ≤ n ≤ 676]）——能带来悦耳度奖励的字母对数量。接下来的 #cf_span[n] 行每行描述一个这样的字母对 «#cf_span[x] #cf_span[y] #cf_span[c]»，表示序列 #cf_span[xy] 会带来奖励 #cf_span[c]（#cf_span[x, y] 为小写拉丁字母，#cf_span[ - 1000 ≤ c ≤ 1000]）。保证输入数据中不会出现重复的字母对 #cf_span[x] #cf_span[y]。"},{"iden":"output","content":"输出一个数字——新角色名字可能达到的最大悦耳度。"},{"iden":"examples","content":"输入\nwinner 4\n4\ns e 7\no s 8\nl o 13\no o 8\n输出\n36\n\n输入\nabcdef 1\n5\na b -10\nb c 5\nc d 5\nd e 5\ne f 5\n输出\n20"},{"iden":"note","content":"在第一个例子中，最悦耳的名字将是 #cf_span[looser]。可以轻松计算出其悦耳度为 36。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ s \\in \\Sigma^+ $ be the initial string of length $ m $, where $ \\Sigma $ is the set of lowercase Latin letters.  \nLet $ k \\in \\mathbb{Z}_{\\geq 0} $ be the maximum number of letters that may be changed.  \nLet $ \\mathcal{B} \\subseteq \\Sigma \\times \\Sigma \\times \\mathbb{Z} $ be a finite set of bonus triples: for each $ (x, y, c) \\in \\mathcal{B} $, the adjacent pair $ xy $ contributes bonus $ c $ to the euphony.  \nDefine the bonus function $ c: \\Sigma \\times \\Sigma \\to \\mathbb{Z} $ such that:  \n$$\nc(x, y) = \n\\begin{cases}\nc & \\text{if } (x, y, c) \\in \\mathcal{B}, \\\\\n0 & \\text{otherwise}.\n\\end{cases}\n$$\n\n**Constraints**  \n1. $ 1 \\leq |s| = m \\leq 100 $  \n2. $ 0 \\leq k \\leq 100 $  \n3. $ 0 \\leq |\\mathcal{B}| = n \\leq 676 $  \n4. For all $ (x, y, c) \\in \\mathcal{B} $, $ -1000 \\leq c \\leq 1000 $, and no duplicate $ (x, y) $ pairs.\n\n**Objective**  \nFind a string $ s' \\in \\Sigma^m $ such that:  \n- $ s' $ differs from $ s $ in at most $ k $ positions:  \n  $$\n  \\left| \\{ i \\in \\{1, \\dots, m\\} \\mid s_i \\ne s'_i \\} \\right| \\leq k\n  $$  \n- The total euphony is maximized:  \n  $$\n  \\text{Euphony}(s') = \\sum_{i=1}^{m-1} c(s'_i, s'_{i+1})\n  $$  \nOutput the maximum possible value of $ \\text{Euphony}(s') $.","simple_statement":null,"has_page_source":false}