← 返回题目列表

Codeforces · 1120/F

F. 秘密信件

中文机器翻译题面 查看原题

小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$$$ 橡子。