C. LionAge II

Codeforces

IDCF73C

Time2000ms

Memory256MB

Difficulty—

English · Original

Chinese · Translation

Formal · Original

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. [samples] ## Note In the first example the most euphony name will be _looser_. It is easy to calculate that its euphony is 36.

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 角色名字所能获得的最大悦耳度。第一行包含角色的名字 #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]。输出一个数字——新角色名字可能达到的最大悦耳度。在第一个例子中，最悦耳的名字将是 #cf_span[looser]。可以轻松计算出其悦耳度为 36。 ## Input 第一行包含角色的名字 #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]。 ## Output 输出一个数字——新角色名字可能达到的最大悦耳度。 [samples] ## Note 在第一个例子中，最悦耳的名字将是 #cf_span[looser]。可以轻松计算出其悦耳度为 36。

**Definitions** Let $ s \in \Sigma^+ $ be the initial string of length $ m $, where $ \Sigma $ is the set of lowercase Latin letters. Let $ k \in \mathbb{Z}_{\geq 0} $ be the maximum number of letters that may be changed. Let $ \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. Define the bonus function $ c: \Sigma \times \Sigma \to \mathbb{Z} $ such that: $$ c(x, y) = \begin{cases} c & \text{if } (x, y, c) \in \mathcal{B}, \\ 0 & \text{otherwise}. \end{cases} $$ **Constraints** 1. $ 1 \leq |s| = m \leq 100 $ 2. $ 0 \leq k \leq 100 $ 3. $ 0 \leq |\mathcal{B}| = n \leq 676 $ 4. For all $ (x, y, c) \in \mathcal{B} $, $ -1000 \leq c \leq 1000 $, and no duplicate $ (x, y) $ pairs. **Objective** Find a string $ s' \in \Sigma^m $ such that: - $ s' $ differs from $ s $ in at most $ k $ positions: $$ \left| \{ i \in \{1, \dots, m\} \mid s_i \ne s'_i \} \right| \leq k $$ - The total euphony is maximized: $$ \text{Euphony}(s') = \sum_{i=1}^{m-1} c(s'_i, s'_{i+1}) $$ Output the maximum possible value of $ \text{Euphony}(s') $.

Samples

Input #1

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

Output #1

Input #2

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

Output #2

API Response (JSON)

{
  "problem": {
    "name": "C. LionAge II",
    "description": {
      "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 str",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF73C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "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 str...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Vasya 正在玩《LionAge II》。他厌倦了和愚蠢的电脑对战，于是安装了这款流行的 MMORPG，以便与朋友对战。Vasya 为他的角色想了一个名字——一个由小写拉丁字母组成的非空字符串 #cf_span[s]。然而，为了避免在朋友面前出风头，Vasya 决定最多修改 #cf_span[k] 个字母，使新名字听起来尽可能悦耳。一个字符串的悦耳度定义如下：对于每一对相邻字母 #cf_span...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**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 let...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments