Minimizing Total Dissatisfaction in the Exam Hall

There is a long, narrow auditorium with \(n\) rows (numbered from 1 to \(n\)) and 6 seats in each row, divided into two groups by an aisle between seats C and D. In every row the left side contains seats A, B, C (from left to right) and the right side contains seats D, E, F (from left to right). Two secure rooms are located outside the hall – one in front of row 1 and one behind row \(n\). Initially every seat is occupied by exactly one candidate.

During the exam, \(m\) different candidates leave the hall one by one. The \(i\)th candidate leaves from seat \(r_i c_i\), where \(c_i\) is a letter from A to F. When a candidate leaves, they must travel first through their row and then along the corridor to one of the secure rooms. While leaving the row, a candidate must pass by any candidate still seated between their seat and the aisle. Specifically:

• For a candidate on the left side (seats A, B, C): if seated at A, they pass seats B and C; if at B, they pass C; if already at C then no one is passed.
• For a candidate on the right side (seats D, E, F): if seated at F, they pass seats E and D; if at E, they pass D; if at D then no one is passed.

After reaching the aisle, the candidate must traverse the corridor. The corridor part is computed as follows. The candidate may choose either secure room:

• If the candidate chooses the front secure room, they will pass by, in every row from 1 to \(r_i-1\), the candidate sitting in the aisle-adjacent seat (seat C for candidates from the left side and seat D for candidates from the right side), provided that seat is still occupied.
• If they choose the back secure room, they will pass by every candidate in rows \(r_i+1\) to \(n\) in the corresponding aisle-adjacent seat.

Let \(A\) and \(B\) be two given constants, and define the dissatisfaction incurred by a leaving candidate as

[ \text{dissatisfaction} = A \times (x) + B \times (y), ]

where:

• \(x\) is the total number of candidates passed (both while leaving the row and along the corridor), and
• \(y\) is the number of candidates already waiting in the chosen secure room when the candidate arrives.

If a candidate does not leave, their dissatisfaction is 0. The candidates cooperate and decide which secure room to use (front or back) on their turn (the order of departures is fixed) so as to minimize the total dissatisfaction.

Your task is to compute the minimum total dissatisfaction over all \(m\) departures. Note that when counting passed candidates, only those who are still seated (or still in the corridor) are counted. In particular, if a candidate has already left (or their corresponding corridor seat is empty), they are not counted.

Input in brief:

• First line: four integers \(n\), \(m\), \(A\), and \(B\).
• Next \(m\) lines: each contains an integer \(r_i\) and a character \(c_i\) indicating the seat from which the candidate leaves.

Output: Output a single integer – the minimum total dissatisfaction.

inputFormat

The first line contains four integers: (n), (m), (A), and (B). Each of the following (m) lines contains an integer (r_i) and a character (c_i) (one of A, B, C, D, E, F), representing the seat of the candidate that leaves in that order.

outputFormat

Output a single integer, the minimum total dissatisfaction.

sample

3 2 1 1
2 A
3 F

5