CF1120F.Secret Letters

Little W and Little P decided to send letters to each other regarding the most important events during a day. There are $n$ events during a day: at time moment $t_i$ something happens to the person $p_i$ ($p_i$ is either W or P, denoting Little W and Little P, respectively), so he needs to immediately send a letter to the other person. They can send a letter using one of the two ways:

• Ask Friendly O to deliver the letter directly. Friendly O takes $d$ acorns for each letter.
• Leave the letter at Wise R's den. Wise R values free space, so he takes $c \cdot T$ acorns for storing a letter for a time segment of length $T$. The recipient can take a letter from Wise R either when he leaves his own letter at Wise R's den, or at time moment $t_{n + 1}$, when everybody comes to Wise R for a tea. It is not possible to take a letter from Wise R's den at other time moments. The friends can store as many letters at Wise R's den as they want, paying for each one separately.

Help the friends determine the minimum possible total cost of sending all letters.

小 W 和小 P 决定就一天中发生的最重要事件互相写信。一天中共有 $n$ 个事件：在时刻 $t_i$，某件事发生在人物 $p_i$ 身上（$p_i$ 为 W 或 P，分别代表小 W 和小 P），因此他需要立即给另一个人写一封信。他们可通过以下两种方式寄信：

• 请友善的 O 直接递送信件。友善的 O 每封信收取 $d$ 颗橡果。
• 将信件留在智者 R 的洞穴中。智者 R 珍视空闲空间，因此对每封信件存储时长为 $T$ 的时间段收取 $c \cdot T$ 颗橡果。收信人只能在以下两个时刻之一从智者 R 的洞穴中取走信件：
  （1）当他本人也将自己的信件留在智者 R 的洞穴中时；
  （2）在时刻 $t_{n + 1}$，此时所有人会到智者 R 处饮茶。
  在其他任何时刻均不可从智者 R 的洞穴中取信。朋友们可在智者 R 的洞穴中存放任意数量的信件，且每封信的存储费用单独计算。

请帮助这两位朋友确定寄出所有信件所需的最小总花费。

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 \lt t_{i + 1}$ for all $i$ from $1$ to $n$.

第一行包含三个整数 $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 处饮茶并取走所有剩余信件的时间。

保证对所有 $i$（$1 \leq i \leq n$），均有 $t_i \lt t_{i + 1}$。

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

输出一个整数——所有信件投递的最小可能成本。

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.

第一个样例中的一个最优解如下：

• 在时刻 0，小 P 将信件留在智者 R 的巢穴中。
• 在时刻 1，小 W 将自己的信件留在智者 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$ 颗橡果。