放假期间，小蓝与电脑对垒，玩起了一款经典的游戏：“ 石头剪刀布” 。游戏规则想必大家已经
非常熟悉了：两边一样则为平局，否则石头胜于剪刀；剪刀胜于布；布胜于石头。小蓝与电脑的对垒
一共有 n 个回合，平局或败局得分为 0；胜局得分取决于小蓝出手的阵容， 剪刀、石头、布各有不同
的分值：
出手“ 石头” 赢的话得 r 点分值；
出手“ 剪刀” 赢的话得 s 点分值；
出手“ 布” 赢的话得 c 点分值；
但是，在第 i 回合中，小蓝不能使用在第（ i-k） 个回合中使用的阵容。 （在前 k 个回合中，小
蓝可以使用任何阵容。）
在游戏开始之前，电脑已经事先安排好了每回合比赛的阵容，而小蓝居然未卜先知了电脑的阵
容！电脑的出手阵容用字符串 t 给出，如果 t 的第 i 个字符（ 1≤i≤n）为 r，则代表电脑将在第 i 个
回合中出手“ 石头” 。同样，c 和 s 分别代表“ 布” 和“ 剪刀” 。
那么请你计算一下，小蓝在游戏中可以获得的最大分值是多少？

n k
r s c
t
其中：n,k,r,s,c 都是整数，t 是字符串。
2≤n≤20
1≤k≤n−1
1≤r,s,c≤1000
字符串 t 的长度是 n

小蓝在游戏中可以获得的最大分值。

样例说明：
机器出手的阵容是：石头、 剪刀、 石头、 布、 石头
则小蓝出手：布、 石头、 石头、 剪刀、 布，分值为6+8+0+7+6=27分
第3回合里，小蓝不能再出第（ 3-2=1）回合里出过的“布”了，所以选择了平局，出手“石
头”，得0分。

28初级算法-模拟 蓝桥杯