题目描述

在一个游戏厅里，高桥正在玩一个叫做 RPS Battle 的游戏，游戏规则如下：

• 玩家与机器进行 $N$ 轮的石头剪刀布游戏（关于石头剪刀布的描述请见注释部分。平局也算作一轮）。
• 每次玩家获胜一轮时，根据他/她使用的手势不同，可以获得以下积分（平局或失利没有积分）：
  • 使用石头获胜可获得 $R$ 分；
  • 使用剪刀获胜可获得 $S$ 分；
  • 使用布获胜可获得 $P$ 分。
• 然而，在第 $i$ 轮中，玩家不能使用与第 $(i-K)$ 轮相同的手势。（在前 $K$ 轮中，玩家可以使用任意手势）

在游戏开始之前，机器决定了每一轮它将要出的手势。通过超能力，高桥成功地读取到了所有的手势。

高桥获得的数据以字符串 $T$ 的形式给出。如果 $T$ 的第 $i$ 个字符 $(1 \\leq i \\leq N)$ 是 r，则表示机器在第 $i$ 轮出石头。同样的，p 和 s 分别表示机器出布和剪刀。

通过选择每轮要出的手势，能够获得的最大总积分是多少？

注释

在这个问题中，石头剪刀布可以看作是一个两人对战的游戏，每个玩家同时用一只手选择石头、剪刀或者布。

• 如果一个玩家选择了石头，另一个玩家选择了剪刀，选择石头的玩家获胜；
• 如果一个玩家选择了剪刀，另一个玩家选择了布，选择剪刀的玩家获胜；
• 如果一个玩家选择了布，另一个玩家选择了石头，选择布的玩家获胜；
• 如果两个玩家选择相同的手势，平局。

约束条件

• $2 \\leq N \\leq 10^5$
• $1 \\leq K \\leq N-1$
• $1 \\leq R,S,P \\leq 10^4$
• $N,K,R,S$ 和 $P$ 都是整数。
• $|T| = N$
• $T$ 由小写字母 r、p 和 s 组成。

输入

从标准输入读入输入数据，格式如下：

$N$ $K$ $R$ $S$ $P$ $T$

输出

打印游戏中可以获得的最大总积分。

示例输入 1

5 2
8 7 6
rsrpr

示例输出 1

27

机器出的手势序列为 {石头, 剪刀, 石头, 布, 石头}。

我们可以使用 {布, 石头, 石头, 剪刀, 布} 对抗机器，获得 $27$ 分。无法获得更多的积分，所以答案是 $27$。

示例输入 2

7 1
100 10 1
ssssppr

示例输出 2

211

示例输入 3

30 5
325 234 123
rspsspspsrpspsppprpsprpssprpsr

示例输出 3

4996