题目描述

你正在游玩一款音乐游戏，一首歌共有 $n$ 个音符，按时间顺序给出。

对于每个音符，你会得到如下三种判定之一：

• $\texttt{P}$（Perfect）：获得 $p$ 分；
• $\texttt{G}$（Good）：获得 $g$ 分；
• $\texttt{M}$（Miss）：获得 $0$ 分。

除了判定本身得到的分数之外，还有连击加分。

我们称一个连击段为一段连续的音符区间，并且在这段区间中不存在判定为 \texttt{M} 的音符。
设 $C$ 为所有连击段中长度的最大值（即整首歌中最多有多少个连续音符的判定都不是 \texttt{M}）。

连击加分定义为 $k \cdot C$，其中 $k$ 为给定的整数参数。

整首歌的总得分为 $n$ 个音符的判定分数之和再加上连击加分 $k \cdot C$。 你完成了一首歌曲的游玩，请你计算这一局的总得分。

输入格式

第一行包含四个整数 $n, p, g, k$ ($1 \leq n \leq 2 \cdot 10^5$，$0 \leq g \leq p \leq 10^3$，$0 \leq k \leq 10^3$) — 音符个数、判定为 $\texttt{P}$ 时得到的分数、判定为 $\texttt{G}$ 时得到的分数以及连击参数 $k$。

第二行包含一个长度为 $n$ 的字符串 $s$，仅由字符 $‘\texttt{P}’$、$‘\texttt{G}’$ 和 $‘\texttt{M}’$ 组成 — 按时间顺序每个音符的判定结果。

输出格式

输出一个整数，表示游玩这首乐曲的总得分。

样例

10 100 75 50
PPPGMGPPPG

1075

2 1 0 1
PP

4