题目描述

本题译自 CCC 2014 Stage2 Day2 T2「Early Exam Evacuation」

你正在一个狭窄而又长的礼堂里考试，礼堂一共有 $N$ 排，标号从前到后分别为 $1$ 到 $N$。每排有 $6$ 个座位，左边 $3$ 个，右边 $3$ 个，中间是过道。每个座位都有一个从 A 到 F 的字母标识，其中最左的座位的标识是 A，最右的座位的标识是 F，过道在座位标识为 C 和 D 的座位之间，礼堂同时还有两个保密室，一个在最前面（第一排前面），一个在最后面（第 $N$ 排后面）。

礼堂里的每个座位一开始被刚好一个考生占用。然而，在考试过程中，$M$ 个不同的考生决定完成所有他们会做的题后依次离开礼堂。第 $i$ 个考生在座位 $R_iC_i$，其中 $C_i$是 A 到 F 的字母之一。当考生离开礼堂时，他们必须在任意一个保密室等待到考试结束。幸运的是，保密室能容下任意多的考生。

考生不仅关心试题本身，他们还关心怎么样可以最舒服的考试。因此，他们协作以最小化他们的不满度之和。一个考生的不满度的计算方式是 $Ax+By$，其中 $A,B$ 为常数，$x$ 为去往保密室时经过的考生人数，具体将在下面详述，$y$ 是在考生进入保密室之前保密室内的人数。注意如果一个考生不离开他的考位，那么他的不满度为 $0$。

当一个考生从一个考位走往保密室时，他在去往过道时必须先经过同排的考生，然后走过从这行到第一行或第 $N$ 行（取决于所选的保密室）的邻近过道的考生。注意走过空的座位不影响 $x$ 值。

你能帮助他们最小化他们的不满度之和吗？

输入格式

第一行四个整数 $N,M,A,B$，以空格分隔，分别表示礼堂内的排数、提前离开的考生数、不满度计算参数。

接下来 $M$ 行每行一个整数 $R_i$ 和一个字母 $C_i$，其中 $1\le i \le N$。

输出格式

输出一个整数，表示最小的不满度之和。

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

55

其中一个最优策略是，第一个提前离开的考生去最前面的保密室，经过 $6$ 个考生（分别是 3D、3C、 2D、 2C、 1D、 1C），不满度为 $3\times 6+4\times 0=18$。第二个提前离开的考生也去最前面的保密室，只经过 $1$ 个考生，即 1C，然后他发现保密室里有 $1$ 个考生，不满度为 $3\times 1+4\times 1=7$。第三个提前离开的考生去最后面的保密室，经过 $1$ 个考生，不满度为 $3$。第四个提前离开的考生去最前面的保密室，经过 $1$ 个考生（因为座位 1D 是空的），不满度为 $11$。最后，第五个提前离开的考生去最后面的保密室，经过 $4$ 个考生，发现保密室里有 $1$ 个人，不满度为 $16$。所有考生总的不满度为 $18+7+3+11+16=55$。

数据范围与提示

对于 $60\%$ 的数据，$1\le M \le 5000$；

对于 $100\%$ 的数据，$1\le N\le 10^5,$ $1\le M \le 6N,$ $1\le A,B\le 10^9,$ $1\le R_i \le N,$ $C_i\in$ A $...$ F。