题目描述

在一家游乐场，高桥正在玩一款名为“RPS Battle”的游戏，游戏规则如下:

玩家与机器进行$N$轮的“石头剪刀布“游戏(关于“石头剪刀布”的描述请参见注释部分。平局也算作一轮)

每当玩家赢得一轮游戏时，根据他/她出的手势，他/她能获得以下分数(平局或输掉的局不记分):

。石头获胜得R分; 。剪刀获胜得S分; 。布获胜得P分。

然而，在第$i$轮中，玩家不能使用在第$(i - K)$轮中使用的手势(在前$K$轮中，玩家可以使用任意手势)。

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

高桥获得的信息用字符串$T$表示。

如果$T$的第$i$个字符$(1 \leq i \leq N )$是r，那么机器将在第$i$轮出石头;类似地，p和s分别代表纸和剪刀。

在每一轮游戏中，通过适当地选择每次出的手势，能够获得的最大总分是多少?

输入

第一行两个整数$N,K$

第二行输出三个整数$R,S,P$

第三行一个整数$T$

5 2
8 7 6
rsrpr

27

7 1
100 10 1
ssssppr

211

30 5
325 234 123
rspsspspsrpspsppprpsprpssprpsr

4996

提示

• $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$

在该问题中，可以将石头剪刀布看作是双人游戏，每个玩家用一只手同时出石头、剪刀或布。

如果一个玩家选择石头而另一个选择剪刀，选择石头的玩家获胜；

如果一个玩家选择剪刀而另一个选择纸，选择剪刀的玩家获胜；

如果一个玩家选择纸而另一个选择石头，选择纸的玩家获胜；

如果两个玩家出相同的手势，那么就是平局。