小W和小P决定就一天中最重要的事件互相写信。一天中有$$$n$$$事件:在$$$t_i$$$时刻$$$p_i$$$发生了什么事($$$p_i$$$要么是W,要么是P,分别表示小W和小P),所以他需要立即给对方发一封信。他们可以使用以下两种方式之一发送信件:
- 请友好O直接递送这封信。友善的 O 为每个字母收取 $$$d$$$ 橡子。
- 将信留在 Wise R 的书房。 Wise R 重视可用空间,因此他使用 $$$c \cdot T$$$ 橡子来存储长度为 $$$T$$$ 的时间段的字母。收件人可以在他把自己的信留在 Wise R 的书房时,或者在 $$$t_{n + 1}$$$ 时刻(当每个人都来 Wise R 喝茶时)从 Wise R 那里取信。其他时间是不可能从 Wise R 的巢穴拿走信件的。朋友们可以在 Wise R 的书房里存放任意数量的信件,并为每封信件单独付费。
帮助朋友们确定发送所有信件的最低可能总费用。
输入
第一行包含三个整数 $$$n, c, d$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq c \leq 10^2$$$, $$$1 \leq d \leq 10^8$$$) – 字母的数量,在 Wise R 的书房存储一个字母一个时间单位的成本和通过Friendly O 寄信的费用。
接下来的 $$$n$$$ 描述事件。其中第 $$$i$$$ 包含一个整数 $$$t_i$$$ 和一个字符 $$$p_i$$$($$$0 \leq t_i \leq 10^6$$$,$$$p_i$$$ 是 W 或 P)——第 $$$i$$$ 事件发生的时间以及事件发生的人。
最后一行包含一个整数 $$$t_{n + 1}$$$ ($$$0 \leq t_{n+1} \leq 10^6$$$) - 每个人都来 Wise R 喝茶并拿走所有剩余字母的时间。
对于从 $$$1$$$ 到 $$$n$$$ 的所有 $$$i$$$,保证 $$$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
注意
第一个示例中的最佳解决方案之一:
- 在时间点 0,小 P 将信留在了 Wise R 的书房。
- 在时刻1,小W把他的信留在了Wise R的书房,并拿走了小P的信。这封信从时间点 0 到时间点 1 位于书房,花费 $$$1$$$ 橡子。
- 在时间点 3 小 P 通过友善 O 发送他的信,花费 $$$4$$$ 橡子。
- 在时间点5,小P把他的信留在书房,收到了小W的信,存储费用为4个橡子。
- 在 8 时刻,小 P 在书房里又留下了一封信。
- 在时间点 10,小 W 来到书房喝茶并收到两封信,支付了 5 和 2 个橡子。
因此,总配送成本为 $$$1 + 4 + 4 + 5 + 2 = 16$$$ 橡子。