Description

You are taking an exam in a narrow and long exam hall. The hall has $n$ rows, numbered from $1$ to $n$ from front to back. Each row has $6$ seats: $3$ on the left and $3$ on the right, with an aisle in the middle. Each seat is labeled with a letter from A to F: the leftmost seat is A, the rightmost seat is F, and the aisle is between seats C and D. The hall also has two waiting rooms: one at the very front (in front of row $1$) and one at the very back (behind row $n$).

Initially, every seat in the hall is occupied by exactly one student. However, during the exam, $m$ different students decide to leave the hall one by one after finishing all the problems they can do. Student $i$ sits at seat $r_i c_i$, where $c_i$ is one of the letters A to F. When a student leaves the hall, they must wait in one of the waiting rooms until the exam ends. Fortunately, the waiting rooms can hold any number of students.

Students not only care about the exam itself, but also about how to take the exam as comfortably as possible. Therefore, they cooperate to minimize the sum of their dissatisfaction. A student’s dissatisfaction is calculated as $Ax+By$, where $A,B$ are constants, $x$ is the number of students they pass on the way to the waiting room (defined in detail below), and $y$ is the number of people already in that waiting room before the student enters it. Note that if a student does not leave their seat, then their dissatisfaction is $0$.

When a student walks from their seat to a waiting room, they must first pass the students in the same row while moving toward the aisle, and then pass the students in the adjacent aisle seats from that row up to row $1$ or row $n$ (depending on which waiting room they choose). Note that passing empty seats does not affect the value of $x$.

Can you help them minimize the sum of their dissatisfaction?

Input Format

The first line contains four integers $n,m,A,B$, separated by spaces, representing the number of rows in the hall, the number of students who leave early, and the parameters in the dissatisfaction formula.

The next $m$ lines each contain an integer $r_i$ and a letter $c_i$, where $1\le i\le n$.

Output Format

Output one integer, the minimum possible total dissatisfaction.

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

55

Hint

One optimal strategy is as follows. The first student who leaves early goes to the front waiting room, passing $6$ students (3D, 3C, 2D, 2C, 1D, 1C), so the dissatisfaction is $3\times6+4\times0=18$. The second student also goes to the front waiting room, passing only $1$ student, 1C, and then finds that there is $1$ student in the waiting room, so the dissatisfaction is $7$. The third student goes to the back waiting room, passing $1$ student, so the dissatisfaction is $3$. The fourth student goes to the front waiting room, passing $1$ student (because seat 1D is empty), so the dissatisfaction is $11$. Finally, the fifth student goes to the back waiting room, passes $4$ students, finds that there is $1$ person in the waiting room, so the dissatisfaction is $16$. The total dissatisfaction of all students is $55$.

Constraints: for $60\%$ of the testdata, $1\le m\le5000$.

For $100\%$ of the testdata, $1\le n\le 10^5$, $1\le m\le6n$, $1\le A,B\le 10^9$.

Translated by ChatGPT 5