← 返回题目列表

AtCoder · abc149_d

D. 预测与限制

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

在一家游戏厅,高桥正在玩一款名为 RPS之战,播放如下:

  • 玩家玩 N 几轮剪刀石头布对着机器。 (关于剪刀石头布的说明,请参见注释。平局也算一局。)
  • 玩家每次赢得一轮比赛,根据他/她使用的手牌,他/她将获得以下分数(平局或失败不得分):
    • R 与 Rock 一起获胜的积分;
    • S 用剪刀获胜的积分;
    • P 用纸获胜的积分。
  • 然而,在 i-第回合,玩家不能使用他/她在该回合中使用过的手 (i-K)-第轮。 (在第一个 K 轮,玩家可以使用任何手牌。)

游戏开始前,机器决定每轮要玩的手牌。高桥凭借超自然的力量,成功地读懂了所有这些手牌。

Takahashi获得的信息以字符串形式给出 T。如果 i- 第一个字符 T (1 \leq i \leq N) is r,机器将在 i-第轮。同样, p 和 s 分别代表布和剪刀。

通过充分选择每一轮的牌局,游戏中的最高总分是多少?

注释

在这个问题中,剪刀石头布可以被认为是一个两人游戏,其中每个玩家同时用手形成石头、剪刀、布。

  • 如果一方选择石头,另一方选择剪刀,则选择石头的玩家获胜;
  • 如果一个玩家选择剪刀而另一个玩家选择布,则选择剪刀的玩家获胜;
  • 如果一方选择纸,另一方选择石头,则选择纸的玩家获胜;
  • 如果两名玩家打同一手牌,则为平局。

约束

  • 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, p,和 s.

输入

输入由标准输入按以下格式给出:

N K
R S P
T

输出

打印游戏中获得的最高总分。


示例输入 1

5 2
8 7 6
rsrpr

示例输出 1

27

机器将播放{石头、剪刀、石头、布、石头}。

例如,我们可以对它玩{布,石头,石头,剪刀,布}来赚取 27 点。 我们无法赚取更多积分,所以答案是 27.


示例输入 2

7 1
100 10 1
ssssppr

示例输出 2

211

示例输入 3

30 5
325 234 123
rspsspspsrpspsppprpsprpssprpsr

示例输出 3

4996