你发现自己正在一个长而窄的礼堂里参加考试——礼堂共有 $N$（$1 \le N \le 10^5$）排座位，从前到后依次编号为 $1 \dots N$。每排有 6 个座位，走廊从礼堂正中间穿过，走廊两侧各有 3 个座位。每个座位由其排号和紧随其后的一个字母（“A” 到 “F”）唯一标识，表示它在该排中的位置（其中 “A” 座位在最左侧，“F” 座位在最右侧）。走廊位于每排的 “C” 和 “D” 座位之间。礼堂还有两个安全室——一个在最前面（第 1 排前面），另一个在最后面（第 $N$ 排后面）。

起初，礼堂里的每个座位都恰好坐着一名考生。然而，在考试过程中，有 $M$ 名不同的考生决定尽早交卷，并希望一个接一个地离开礼堂。第 $i$ 个离开的考生坐在座位 $R_i C_i$（$1 \le R_i \le N$，$C_i$ 为 “A”..“F” 之一）。当考生离开礼堂时，他们必须待在其中一个安全室中直到考试结束。幸运的是，两个安全室都可以容纳任意多的人。

考生们不仅关心考试，还希望自己的生活尽可能便利——因此，他们希望通过通力合作，使所有人体验到的总不便度最小。单个考生体验到的不便度为 $Ax + By$，其中 $A$ 和 $B$ 是给定的常数（$0 \le A, B \le 10^9$），$x$ 是在前往所选安全室的路上经过的不同人数（详见下文），$y$ 是在该考生进入该安全室之前，该安全室中已有的总人数。请注意，如果考生不离开座位，他们的不便度为 0。

当从座位走向安全室时，考生必须首先在前往走廊的路上经过同排的其他考生，然后经过从该排到第 1 排或第 $N$ 排（取决于选择哪个安全室）之间（含两端）所有与走廊相邻座位上的考生。请注意，沿途经过的任何空座位不计入此人数。

你能帮助这些可怜的考生，让他们的生活尽可能便利吗？

输入格式

第一行包含四个由空格分隔的整数：$N$（$1 \le N \le 10^5$），表示礼堂的排数；$M$（$1 \le M \le 6N$），表示提前离开的考生人数；以及 $A$ 和 $B$（$1 \le A, B \le 10^9$），用于确定考生提前离开所造成的不便度的常数。

接下来的 $M$ 行，每行包含一个整数和一个字符 $R_i$ 和 $C_i$，按顺序表示第 $i$ 个离开的考生所在的座位，其中 $1 \le R_i \le N$ 且 $C_i \in \{\text{"A"}\dots\text{"F"}\}$。

你可以假设，对于占总分 60% 的测试用例，$M \le 5000$。

输出格式

输出一个整数，表示所有 $M$ 名提前离开的考生所体验到的最小总不便度。

样例

输入样例 1

5 5 3 4
3E
1D
5C
1E
4A

输出样例 1

55

说明

一种最优策略如下。

第一个离开的人可以去前方的安全室，沿途经过六个人（分别在座位 3D、3C、2D、2C、1D 和 1C），产生的不便度为 $3 \cdot 6 + 4 \cdot 0 = 18$。

第二个离开的人也可以去前方的安全室，只需经过一个人（在座位 1C），并发现安全室里已经有一个人，产生的不便度为 $3 \cdot 1 + 4 \cdot 1 = 7$。

第三个人可以去后方的安全室，经过一个人，产生的不便度为 3。

第四个人可以加入前方的安全室（与前两个人一起），只需经过一个人（因为此时座位 1D 已经是空的），产生的不便度为 11。

最后，第五个离开的人可以去后方的安全室，经过四个人，并在后方安全室遇到一个人，产生的不便度为 16。

使用该策略，考生体验到的总不便度为 $18 + 7 + 3 + 11 + 16 = 55$。