Secret Letters

Description:

Input:

The first line contains three integers $$$n, c, d$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq c \leq 10^2$$$, $$$1 \leq d \leq 10^8$$$) — the number of letters, the cost of storing a letter for one time unit at Wise R's den and the cost of delivering a letter via Friendly O.

The next $$$n$$$ describe the events. The $$$i$$$-th of them contains an integer $$$t_i$$$ and a character $$$p_i$$$ ($$$0 \leq t_i \leq 10^6$$$, $$$p_i$$$ is either W or P) — the time the $$$i$$$-th event happens and the person the event happens to.

The last line contains a single integer $$$t_{n + 1}$$$ ($$$0 \leq t_{n+1} \leq 10^6$$$) — the time when everybody comes to Wise R for a tea and takes all remaining letters.

It is guaranteed that $$$t_i < t_{i + 1}$$$ for all $$$i$$$ from $$$1$$$ to $$$n$$$.

Output:

Print a single integer — the minimum possible cost of delivery of all letters.

Sample Input:

5 1 4
0 P
1 W
3 P
5 P
8 P
10

Sample Output:

16

Sample Input:

10 10 94
17 W
20 W
28 W
48 W
51 P
52 W
56 W
62 P
75 P
78 P
87

Sample Output:

916

Note:

One of optimal solutions in the first example:

• At time moment 0 Little P leaves the letter at Wise R's den.
• At time moment 1 Little W leaves his letter at Wise R's den and takes Little P's letter. This letter is at the den from time moment 0 to time moment 1, it costs $$$1$$$ acorn.
• At time moment 3 Little P sends his letter via Friendly O, it costs $$$4$$$ acorns.
• At time moment 5 Little P leaves his letter at the den, receiving Little W's letter which storage costs 4 acorns.
• At time moment 8 Little P leaves one more letter at the den.
• At time moment 10 Little W comes to the den for a tea and receives the two letters, paying 5 and 2 acorns.

The total cost of delivery is thus $$$1 + 4 + 4 + 5 + 2 = 16$$$ acorns.