您正在玩一款新的著名格斗游戏:Kortal Mombat XII。你必须对对手的性格施以残酷的对待。
您正在新一代游戏机上玩游戏,因此您的游戏手柄有 $$$26$$$ 按钮。每个按钮上都写有一个小写拉丁字母,从“a”到“z”。按钮上的所有字母都是成对不同的。
您将获得一系列命中,第 $$$i$$$ 次命中会对对手角色造成 $$$a_i$$$ 单位的伤害。要执行第 $$$i$$$ 次点击,您必须按下游戏手柄上的 $$$s_i$$$ 按钮。点击数从 $$$1$$$ 到 $$$n$$$。
你知道,如果你连续按下某个按钮超过 $$$k$$$ 次,那么它就会损坏。您很珍惜您的游戏手柄,并且不想损坏其任何按钮。
要实施残暴,你必须击中给定序列的一些命中。您可以跳过其中任何一个,但禁止更改序列的初始顺序。造成的总伤害是未跳过的所有 $$$i$$$ 命中的 $$$a_i$$$ 总和。
请注意,如果您跳过点击,则连续按下按钮的计数器将不会重置。
你的任务是跳过一些攻击,对对手角色造成最大可能的总伤害,并且不破坏游戏手柄按钮。
输入
输入的第一行包含两个整数 $$$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$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 次命中的伤害。
输入的第三行包含字符串 $$$s$$$,由 $$$n$$$ 小写拉丁字母组成 - 命中序列(每个字符是您需要按下以执行相应命中的按钮上的字母)。
输出
打印一个整数 $$$dmg$$$ — 在不破坏游戏手柄按钮的情况下可以对对手角色造成的最大可能伤害。
示例
输入 #1
7 3 1 5 16 18 7 2 10 baaaaca
输出 #1
54
输入 #2
5 5 2 4 1 3 1000 aaaaa
输出 #2
1010
输入 #3
5 4 2 4 1 3 1000 aaaaa
输出 #3
1009
输入#4
8 1 10 15 2 1 4 8 15 16 qqwweerr
输出#4
41
输入 #5
6 3 14 18 9 19 2 15 cccccc
输出 #5
52
输入 #6
2 1 10 10 qq
输出 #6
10
注意
在第一个示例中,您可以选择数字 $$$[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$$$。