P6839 [BJOI2016] 打字机

小 J 在搬家的过程中发现了一台古老的打字机。 好奇的小 J 决定研究如何使用它。首先，需要将一条长度为 $m$ 的纸带放入打字机。打字机上共有 26 个按键，分别是小写字母 `a` 到 `z` 。每当你按下一个按键时，打字机 就会立即在纸带上打印出那个字符，并将纸带平移一个单位距离。聪明的小 J 很快就掌握了这款打字机的使用技巧，并想尝试新的挑战。 他拿出了一本字典，挑选了 $n$ 个单词，并给每个单词设定了分数。纸带中每出现一次指定的单词，就会得到对应的分数。例如， 单词 `eye` 的分数为 $2$， `year` 的分数为 $3$，那么纸带 `eyeyeyear` 的分数为 $9$ 分。小 J 希望挑战自己，打出分数最高的纸带。 特别地，小 J 偶尔会手抖，按到自己不想输入的字符。由于这台古老的打字机没有退格（删除）功能，所以小 J 只能接受按错这个事实，重新规划在按错的情况下如何得最高分。倘若小 J 有可能在任意位置按错按键，并保证整个过程中按错的次数不超过 $k$ 次，那么请你算出他在最坏情况下的最高得分是多少。

无

无

【样例解释】 以下是一种错误思路： "共 $4$ 种情况，即第 $1$ 位按错、第 $2$ 位按错、第 $3$ 位按错和第 $4$ 位按错。 1. 第 $1$ 位按错（不妨假设按成 `x`，下同），最高得分为 `xwha`，得分为 $10$。 2. 第 $2$ 位按错，最高得分为 `wxha`，同样为 $10$ 分。 3. 第 $3$ 位按错，最高得分为 `haxw`，同样为 $10$ 分。 4. 第 $4$ 位按错，最高得分为 `hawx`，同样为 $10$ 分。 综上，最坏情况下最高得分为 $10$ 分。" 这种思路的错误之处在于，你不能根据哪一位按错决定你第一位按哪个键。 换种说法，你在哪一位按错，是在按下那个按键之后才能知道的事情。 正确的思路如下： 1. 第 $1$ 位先按 `h`，倘若按对， 跳至 2，倘若按错， 跳至 4； 2. 第 $2$ 位按 `a`，倘若按对， 跳至 3，倘若按错， 跳至 5； 3. 第 $3$ 位和第 $4$ 位都按 `w`， 结束。 至多错 1 次，最终纸带为 `hawx` 或 `haxw`，得分为 $10$ 分。 4. 后面三位依次按 `haw`， 结束。 因为不会再错， 最终纸带为 `xhaw`，得分为 $10$ 分。 5. 后面两位依次按 `ha`， 结束。因为不会再错， 最终纸带为 `hxha`，得分为 $9$ 分。 综上，最坏情况下，最高得分为 $9$ 分。 【数据范围】 测试点 $1,2$ 满足，$n = 1$ 或 $k = 0$； 测试点 $1\sim 6$ 满足，$n ≤ 100$，$m ≤ 500$，$∑|S| ≤ 500$，$a_i ≤1000$； 测试点 $7,8$ 满足，$k = 0$，$∑|S| ≤ 200$； 测试点 $9,10$ 满足，$∑|S| ≤ 50$，$a_i ≤1$。 对于 $100\%$ 的数据，$n ≤ 100$，$m ≤ 10^9$ ，$∑|S| ≤ 500$，$a_i ≤1000$，$k ≤ 5$。**请注意，每一个测试点都有相应特殊性质。**