P7701 [CCC 2014] 提前交卷

你正在一个狭窄而又长的礼堂里考试，礼堂一共有 $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$。

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

其中一个最优策略是，第一个提前离开的考生去最前面的保密室，经过 $6$ 个考生（分别是 `3D`、`3C`、`2D`、`2C`、`1D`、`1C`），不满度为 $3\times6+4\times0=18$。第二个提前离开的考生也去最前面的保密室，只经过 $1$ 个考生，即 `1C`，然后他发现保密室里有 $1$ 个考生，不满度为 $7$。第三个提前离开的考生去最后面的保密室，经过 $1$ 个考生，不满度为 $3$。第四个提前离开的考生去最前面的保密室，经过 $1$ 个考生（因为座位 `1D` 是空的），不满度为 $11$。最后，第五个提前离开的考生去最后面的保密室，经过 $4$ 个考生，发现保密室里有 $1$ 个人，不满度为 $16$。所有考生总的不满度为 $55$。 对于 $60\%$ 的数据，$1\le m\le5000$； 对于 $100\%$ 的数据，$1\le n\le 10^5$，$1\le m\le6n$，$1\le A,B\le 10^9$。