当前没有测试数据。

题目描述

小 A 是一名热爱编程的初中生，最近他开发了一款石头剪刀布的电子游戏。在这款游戏中，玩家需要与电脑进行 $N$ 轮对战。

每一轮，玩家和电脑的出招手势可能是如下三种其中之一：

• r：石头（rock）
• s：剪刀（scissors）
• p：布（paper）

判断输赢的方法，是众所周知的：石头战胜剪刀、剪刀战胜布、布战胜石头。

玩家的目标是：尽可能多地获得分数。在游戏中，玩家赢得每一轮后将获得对应分数：

• 如果用石头赢，得 $A$ 分；
• 如果用剪刀赢，得 $B$ 分；
• 如果用布赢，得 $C$ 分。

为了让游戏更有挑战性，小A设计了一个规则：**你不能在当前轮（第 $i$ 轮）使用和第 $i-K$ 轮相同的手势。**换句话说，手势不能在相隔 $K$ 的回合中重复使用。

在前 $K$ 轮中，你可以任意选择任何手势，不受限制。

给定电脑在每一轮的出招序列，请你计算出，在不违反规则的前提下，玩家最多可以获得多少总分？

输入格式

第一行输入两个整数 $N$ 和 $K$，分别表示对战轮数与限制间隔。

第二行三个整数 $A$、$B$、$C$，分别表示用石头、剪刀、布赢时获得的分数。

第三行一个长度为 $N$ 的字符串，表示电脑在每一轮出的手势，该字符串中仅包含字符 r、s、p。

输出格式

输出一个整数，表示玩家在这款游戏中最多能获得多少分。

样例 #1

输入

5 2
8 7 6
rsrpr

输出

27

样例 #2

输入

7 1
100 10 1
ssssppr

输出

211

样例 #3

输入

30 5
325 234 123
rspsspspsrpspsppprpsprpssprpsr

输出

4996

样例说明

样例 1 解释

电脑的出招手势序列是：r s r p r，你可以按如下方式选择出招（避免与 $i-K$ 重复）：

• 第 1 轮：出布（赢，得 6 分）
• 第 2 轮：出石头（赢，得 8 分）
• 第 3 轮：出石头（平局，得 0 分）
• 第 4 轮：出剪刀（得 7 分）
• 第 5 轮：出布（得 6 分）

总得分为：6 + 8 + 0 + 7 + 6 = 27。

数据范围

对于 $100\%$ 的数据，满足 $2 \le N \le 10^5$，$1 \le K \le N-1$，$1 \le A, B, C \le 10^4$。

测试点	数据范围
$1 \sim 7$	$1 \le N \le 10$，$1 \le K \le 10$
$8 \sim 10$	$K = 1$
$11 \sim 20$	$2 \le N \le 10^5$，$1 \le K \le N-1$