Early Exam Evacuation

Time limit2sMemory limit256 MB

Summary

Each of M writers seated in an N-row auditorium exits front or back to minimize passing plus crowding cost.

Level: Medium7 of 10
Topics: Dynamic programming, Sorting, Prefix sum
Solved: No attempts yet

Problem

An exam is held in an N-row auditorium with six seats A through F per row and an aisle between C and D. Secure rooms sit in front of row 1 and behind row N. M writers leave one by one, each choosing the front or back room. Inconvenience is Ax+By where x is people passed along the route and y is people already in the chosen room. Minimize total inconvenience.

Input

The first line has N, M, A, and B. The next M lines contain Ri and Ci.

Output

Print the minimum total inconvenience.

Examples2

Example 1
Input
```
5 5 3 4
3E
1D
5C
1E
4A
```
Expected output
```
55
```
Example 2
Input
```
1 1 2 3
1A
```
Expected output
```
6
```