Canadian Computing Competition: 2014 Stage 2, Day 2, Problem 2
You find yourself writing an exam in a long, narrow auditorium – it has ~N~ (~1 \le N \le 10^5~) rows, numbered ~1 \dots N~ from the front to the back, each of which has 6 seats, 3 on each side of the aisle running down the middle of the auditorium. Each seat is identified by its row number immediately followed by a letter from
F, which indicates its position in that row (with seat
A at the far left, and
F at the far right). The aisle lies between seats
D in each row. The auditorium also has two secure rooms – one at the front (in front of row 1), and one at the back (behind row ~N~).
Every seat in the auditorium is initially occupied by exactly one exam-writer per seat. However, during the course of the exam, ~M~ different exam writers decide that they have written all they can on the exam, and then would like to leave the auditorium, one after another. The ~i~-th exam writer is in seat ~R_iC_i~ (~1 \le R_i \le N, C_i~ is one of
F). When the exam writer leaves the auditorium, they must stay in one of the secure rooms until the end of the exam. Fortunately, both secure rooms can hold as many people as necessary.
Exam writers not only worry about writing exams, but they would like their lives to be as convenient as possible – as such, they're interested in working together to minimize the total inconvenience experienced by all of them. The inconvenience in a single exam-writer experiences is ~Ax + By~, where ~A~ and ~B~ are given constants (~0 \le A, B \le 10^9~), ~x~ is the number of different people passed on the way to the chosen secure room (explained below), and ~y~ is the number of people already in that secure room before that exam-writer enters. Note that if an exam-writer does not leave their seat, their inconvenience is 0.
When walking from a seat to a secure room, one must first pass any other exam writers in the same row on the way to the aisle, and then any exam writers in seats adjacent to the aisle from that row to either row ~1~ or ~N~ (depending on which secure room is chosen), inclusive. Note that any vacant seats passed along the way don't count towards this value.
Can you help the poor exam writers make their lives as convenient as possible?
The first line contains four space-separated integers: ~N~ (~1 \le N \le 10^5~), the number of rows in the auditorium; ~M~ (~1 \le M \le 6N~), the number of exam writers that leave early; ~A~, followed by ~B~ (~1 \le A, B \le 10^9~), the constants used in determining the inconvenience caused by an exam writer leaving early.
The next ~M~ lines each contain one integer followed by one character, ~R_i~ and ~C_i~, for ~i = 1 \dots N~ in order, where ~1 \le R_i \le N~ and ~C_i \in~
You can assume that for test cases worth 60% of the marks, ~M \le 5000~.
Output the integer which is the minimum total inconvenience experience by all ~M~ exam writers who leave early.
5 5 3 4 3E 1D 5C 1E 4A
Output for Sample Input
Explanation of Output for Sample Input
One optimal strategy is as follows. The first person to leave can go to the front secure room, passing six people along the way (in seats ~3D, 3C, 2D, 2C, 1D~, and ~1C~) for an inconvenience of ~3 \cdot 6 + 4 \cdot 0 = 18~. The second person to leave can also go to the front secure room, passing only one person (in seat ~1C~) and finding one person already in the secure room, for an inconvenience of ~3 \cdot 1 + 4 \cdot 1 = 7~. The third person can go to the back secure room, passing one person for an inconvenience of ~3~. The fourth person can join the first two in the front secure room, passing only one person (as seat ~1D~ is vacant at that point) for an inconvenience of ~11~. Finally, the fifth person to leave can go to the back secure room, passing four people and meeting one person in the back secure room for an inconvenience of ~16~. The total inconvenience experience by the exam writers with this strategy is ~18 + 7 + 3 + 11 + 16 = 55~.