石头剪刀布

题目描述

高桥君决定在游戏厅玩名为「猜拳对战」的游戏。游戏规则如下：

• 玩家与机器猜拳 $N$ 次（平局也算作 $1$ 次猜拳）。
• 玩家猜拳获胜时，根据出拳获得以下分数（平局或落败得 $0$ 分）。
  • 出石头获胜时，得 $R$ 分
  • 出剪刀获胜时，得 $S$ 分
  • 出布获胜时，得 $P$ 分
• 但是，不能出与正好 $K$ 次前的猜拳相同的拳。（前 $K$ 次猜拳可以出任意拳。）

机器在游戏开始前决定每次猜拳要出的拳。作为超能力者的高桥君在游戏开始前读出了全部信息。

高桥君读出的信息以字符串 $T$ 给出。$T$ 的第 $i$（$1 \leq i \leq N$）个字符为 r 时，表示第 $i$ 次猜拳机器出石头；为 s 时表示出剪刀；为 p 时表示出布。

当高桥君最优化选择 $N$ 次猜拳要出的拳时，游戏结束前最多能获得多少分？

输入格式

输入按以下格式从标准输入给出：

$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

数据范围

• $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、s、p 之一。