CF1107C Brutality

在全新的格斗游戏《Kortal Mombat XII》中，你需要对对手的角色实施一招强势的「残暴攻击」。 手柄配备了 $26$ 个按钮，每个按钮上标有不同的小写字母，从 'a' 到 'z'。这意味着每个按钮只能通过对应字母按键激活。 我们有一系列的攻击动作，第 $i$ 次攻击会造成 $a_i$ 点伤害。为了执行第 $i$ 次攻击，你必须按下手柄上的 $s_i$ 按钮。攻击的编号依次为 $1$ 到 $n$。 然而如果连续按下某个按钮超过 $k$ 次，该按钮就会损坏。为了保护你的手柄不被损坏，你需要限制连续按同一按钮的次数。 「残暴攻击」要求你在不改变攻击顺序的前提下选择执行这些攻击动作中的若干次。每一次攻击都可以选择执行或跳过。跳过某次攻击不会重置同一按钮的连续按压次数。 你的任务是：跳过一些攻击，确保在不损坏任何手柄按钮的情况下，达到最大的总伤害值。

第一行输入包含两个整数 $n$ 和 $k$，分别表示攻击次数和连续按相同按钮的最大允许次数（$1 \le k \le n \le 2 \cdot 10^5$）。 第二行输入包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，每个整数代表对应攻击的伤害值（$1 \le a_i \le 10^9$）。 第三行输入的是一个长度为 $n$ 的字符串 $s$，表示各次攻击所需按下的按钮（字符串中的每个字符对应一个按钮上的字母）。

输出一个整数，即在保护手柄按钮的前提下可以造成的最大总伤害。

- 在第一个例子中，你可以选择攻击序列 $[1, 3, 4, 5, 6, 7]$，这样总伤害为 $1 + 16 + 18 + 7 + 2 + 10 = 54$。 - 在第二个例子中，选择全部攻击的总伤害为 $2 + 4 + 1 + 3 + 1000 = 1010$。 - 在第三个例子中，选择除第三次攻击外的其他攻击，总伤害为 $2 + 4 + 3 + 1000 = 1009$。 - 在第四个例子中，选择攻击序列 $[2, 3, 6, 8]$，可以最大化总伤害，即 $15 + 2 + 8 + 16 = 41$。 - 在第五个例子中，选择攻击序列 $[2, 4, 6]$，总伤害为 $18 + 19 + 15 = 52$。 - 在第六个例子中，只能选择第一个或第二个攻击，总伤害为 $10$。 **本翻译由 AI 自动生成**