D - 预测和限制

得分：400分

问题描述

在一家游乐场，高桥正在玩一款名为“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$

输出

输出能够获得的最大总分。

5 2
8 7 6
rsrpr

27

机器将会出{石头，剪刀，石头，纸，石头}。

我们可以选择出{纸，石头，石头，剪刀，纸}与它对抗，从而获得27分。 我们无法获得更多分数，所以答案是27。

7 1
100 10 1
ssssppr

211

30 5
325 234 123
rspsspspsrpspsppprpsprpssprpsr

4996