CF1120F Secret Letters

小 W 和小 P 决定互相发送信件，记录一天中最重要的事件。在一天中共有 $n$ 个事件：在时刻 $t_i$，某件事发生在 $p_i$ 身上（$p_i$ 为 W 或 P，分别表示小 W 和小 P），于是他需要立即给对方发送一封信。他们可以通过以下两种方式发送信件： - 请友好的 O 直接送信。每封信 O 都会收取 $d$ 个橡果。 - 将信件寄存在睿智的 R 的巢穴。R 很重视空间，因此他会按每封信每单位时间 $c$ 个橡果收费。如果一封信在巢穴中存放了 $T$ 个时间单位，则需支付 $c \cdot T$ 个橡果。收信人可以在他自己也来巢穴寄信时，或者在时刻 $t_{n+1}$（大家都来巢穴喝茶的时刻）取走信件。除此之外，不能在其他时刻取信。朋友们可以在 R 的巢穴中存放任意多封信，每封信分别计费。 请帮助朋友们计算，发送所有信件的最小总花费。

第一行包含三个整数 $n, c, d$（$1 \leq n \leq 10^5$，$1 \leq c \leq 10^2$，$1 \leq d \leq 10^8$）——信件数量、在 R 巢穴中每单位时间存放一封信的费用，以及通过 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$），表示大家来 R 巢穴喝茶并取走所有剩余信件的时刻。 保证对于所有 $1 \leq i \leq n$，都有 $t_i < t_{i+1}$。

输出一个整数，表示发送所有信件的最小总花费。

第一个样例的一种最优方案如下： - 在时刻 0，小 P 把信件寄存在 R 的巢穴。 - 在时刻 1，小 W 把信件寄存在 R 的巢穴，并取走小 P 的信件。该信件在巢穴中存放了 $1$ 个时间单位，费用为 $1$ 个橡果。 - 在时刻 3，小 P 通过 O 直接送信，费用为 $4$ 个橡果。 - 在时刻 5，小 P 把信件寄存在巢穴，并取走小 W 的信件，存储费用为 $4$ 个橡果。 - 在时刻 8，小 P 又寄存了一封信。 - 在时刻 10，小 W 来巢穴喝茶，取走两封信，分别支付 $5$ 和 $2$ 个橡果。 因此，总花费为 $1 + 4 + 4 + 5 + 2 = 16$ 个橡果。 由 ChatGPT 4.1 翻译