秘密信件

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

小 W 和小 P 会把一天中发生的重要事件写信告诉对方。一天中共有 $n$ 个事件。第 $i$ 个事件发生在时刻 $t_i$，并发生在人物 $p_i$ 身上，其中 $p_i$ 是 W 或 P。该人物必须立刻写好一封信并选择下列一种寄送方式：

• 请 O 直接把信送给对方，费用为 $d$。
• 把信留在 R 的巢穴中。每封信每存放一个单位时间收费 $c$。收信人下一次自己来 R 处寄信时，会取走写给自己的所有信；如果此前没有取走，则会在时刻 $t_{n+1}$ 大家来喝茶时取走。除此之外不能专程来取信。

R 可以同时保管任意多封信，每封信分别计费。

请计算寄送全部信件的最小总费用。

输入格式

第一行包含三个整数 $n,c,d$，分别表示事件数、每封信每单位时间的保管费和直接送信的费用。

接下来 $n$ 行，每行包含一个整数 $t_i$ 和一个字符 $p_i$，描述第 $i$ 个事件。

最后一行包含一个整数 $t_{n+1}$，表示最终喝茶并取走所有剩余信件的时刻。

保证 $t_i<t_{i+1}$。

输出格式

输出一个整数，表示最小总费用。

样例输入 1

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

样例输出 1

16

样例输入 2

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

样例输出 2

916

数据范围

对于全部数据：$1\le n\le10^5$，$1\le c\le100$，$1\le d\le10^8$，$0\le t_i\le10^6$。

所有子任务均保证输入满足题目叙述中的严格递增条件。