[ABC149D] Prediction and Restriction
题意翻译
你和对手进行 $n$ 次剪刀石头布,已知对方出石头剪刀布的顺序,以及你出石头,剪刀,布赢了后分别能得到的分数,求最多能得到多少分数.
注意,你第 $i-k$ 轮和第 $i(i>k)$ 轮出的手势不能相同.
题目描述
[problemUrl]: https://atcoder.jp/contests/abc149/tasks/abc149_d
高橋君は、ゲームセンターで「じゃんけんバトル」というゲームをプレイすることにしました。このゲームのルールは以下の通りです。
- プレイヤーは筐体と $ 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 $
输出格式
得られる最大の合計スコアを出力せよ。
输入输出样例
输入样例 #1
5 2
8 7 6
rsrpr
输出样例 #1
27
输入样例 #2
7 1
100 10 1
ssssppr
输出样例 #2
211
输入样例 #3
30 5
325 234 123
rspsspspsrpspsppprpsprpssprpsr
输出样例 #3
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 $ を出力します。