AT_abc149_d [ABC149D] Prediction and Restriction

题目描述

高桥君决定在游戏中心玩一款名为“猜拳对战”的游戏。该游戏的规则如下：

• 玩家将与机器进行 $N$ 次猜拳（即使平局也算作一次猜拳）。
• 玩家在猜拳中获胜时，会根据所出的手势获得如下分数（平局或失败得 $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

输出

27

样例 2

输入

7 1
100 10 1
ssssppr

输出

211

样例 3

输入

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 三种字符。

样例解释 1

机器依次出 {石头、剪刀、石头、布、石头}。例如，如果依次出 {布、石头、石头、剪刀、布}，可以获得 $27$ 分。无法获得更高的分数，因此输出 $27$。

由 ChatGPT 4.1 翻译