题目描述

高橋君は、ゲームセンターで「じゃんけんバトル」というゲームをプレイすることにしました。このゲームのルールは以下の通りです。

• プレイヤーは筐体と $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$

输出格式

得られる最大の合計スコアを出力せよ。

题目大意

你和对手进行 $n$ 次剪刀石头布,已知对方出石头剪刀布的顺序,以及你出石头,剪刀,布赢了后分别能得到的分数,求最多能得到多少分数.

注意,你第 $i-k$ 轮和第 $i(i>k)$ 轮出的手势不能相同.

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$
• $T$ に含まれる文字は r , s , p のいずれかである。

Sample Explanation 1

筐体は、{グー、チョキ、グー、パー、グー} と手を出します。 これに対して、例えば {パー、グー、グー、チョキ、パー} と出せば、$27$ 点を獲得できます。 これより大きい点は獲得できないので、$27$ を出力します。