问题描述

高桥君决定玩一个游戏，规则如下：
有 $m$ 种颜色的方块总共有 $n$ 个，每个方块都会依次掉落。
每次方块掉落时，高桥君可以选择将该方块放到一个堆中或者丢弃它。
堆中的方块只能按照顺序堆叠，新掉落的方块必须叠放在已有堆顶的方块上。
当所有方块都掉落完毕后，根据以下规则对堆进行评价：

• 颜色奖励：每种颜色的方块都有特定的得分，根据堆中包含的方块个数来计算。
• 连击奖励：如果同一种颜色的方块连续叠放了 $x$ 个，则根据连击奖励系数 $Y$ 得分为 $Y \times (x-1)$。
• 全色奖励：如果堆中至少包含了每种颜色的方块各一个，则得分为 $Z$。

给定方块的种类和顺序以及评价所需的得分，求最大得分。

输入

输入从标准输入中读取，具体格式如下：$n$ $m$ $Y$ $Z$
$c_1$ $p_1$
$c_2$ $p_2$
:
:
$c_m$ $p_m$
$b_1b_2 ‥‥ b_n$

• 第一行包含以半角空格分隔的四个整数 $n, m, Y, Z$。
  1. $n$ 是方块的数量，满足 $1≦n≦5,000$。
  2. $m$ 是方块的颜色总数，满足 $1≦m≦10$。
  3. $Y$ 是连击奖励系数，满足 $-100≦Y≦100$。
  4. $Z$ 是全色奖励得分，满足 $-10,000≦Z≦10,000$。
  5. $n, m, Y, Z$ 均为整数。
• 接下来的 $m$ 行中，每行包含一个颜色和其对应的颜色奖励得分。
  1. $c_i$ 是第 $i(1≦i≦m)$ 种颜色的方块。
  2. $p_i$ 是对应颜色的颜色奖励得分。
  3. $c_i$ 是大写英文字母(A-Z)，$p_i$ 满足 $-100≦p_i≦100$。
  4. 每种颜色的奖励得分不重复（$x≠y$ 时 $c_x≠c_y$)。
• 第 $m+2$ 行是一个长度为 $n$ 的字符串，表示方块掉落的顺序。
  1. $b_j$ 是第 $j(1≦j≦n)$ 个掉落的方块的颜色。
  2. $b_j$ 只能是 $c_1,c_2,...,c_m$ 中的一个。

输出

将可以获得的最大得分输出到标准输出中，以一行形式输出。
末尾必须输出换行符。

输入样例 1

5 3 3 5
R 1
G 1
B 1
RGBRR

输出样例 1

13

• 如果将所有方块都放入堆中，

  • 颜色奖励：每种颜色的得分都是 $1$，所以得分为 $1$ 点 × $5$ 个方块 $= 5$ 点
  • 连击奖励：因为有 $2$ 个连续的 R 方块，所以得分为 $3×(2-1)=3$ 点
  • 全色奖励：因为每种颜色至少有 $1$ 个方块，所以得分为 $5$ 点

  总得分为 $5+3+5=13$ 点。

• 如果丢弃任何一个方块，得分都会低于 $13$ 点，所以最大得分为 $13$ 点。

输入样例 2

3 3 3 5
R 1
G 3
B 2
RBR

输出样例 2

5

• 将所有方块都放入堆中，

  • 颜色奖励：$2$ 个 $1$ 分的方块 + $1$ 个 $2$ 分的方块 $=4$ 分
  • 没有连续的方块，所以连击奖励和全色奖励都是 $0$ 分

  总得分为 $4$ 分。

• 但是，如果丢弃方块 B，将 RR 放入堆中，

  • 颜色奖励：$2$ 个 $1$ 分的方块 $=2$ 分
  • 连击奖励：$3×(2-1)=3$ 分

  最大得分为 $5$ 分。

输入样例 3

8 3 5 3
R 1
G 1
B 1
RRGRRBRR

输出样例 3

31

• 如图 $(a)$ 所示，总共掉落了 $8$ 个方块。
• 如果将所有方块都放入堆中，如图 $(b)$ 所示，可以得到 $2$ 组连击，每组 $3$ 个。
• 此外，还满足全色奖励条件，所以得分为 $1$ 分 × $8$ 个 + $5$ 分 × $(2-1)$ 个 × $3$ 组 $+ 3$ 分 $= 26$ 分。
• 但是，如果只将 R 方块放入堆中，如图 $(c)$ 所示，可以得到 $1$ 分 × $6$ 个 + $5$ 分 × $(6-1) + 0$ 分 $=