P14877 [ICPC 2019 Yokohama R] Wall Painting

时间限制：6s -> 3s

这里有一面由若干垂直面板构成的墙。这些面板尚未涂色。 你拥有若干个机器人，每个机器人可以用单一颜色（红色、绿色或蓝色）为面板涂色。每个机器人被激活时，会在特定位置到另一个特定位置之间的面板上涂上特定颜色。每个机器人要涂色的面板和涂色颜色是固定的，但哪些机器人被激活以及它们的激活顺序可以任意决定。 你希望墙面被涂色后具有较高的**美学价值**。这里，墙面的美学价值简单地定义为墙面上所有面板的美学价值之和，而单个面板的美学价值定义如下： - $0$，如果面板未被涂色。 - 指定的奖励值，如果面板只被涂上一种颜色，无论被涂了多少次。 - 指定的惩罚值（负值），如果面板先被涂上一种颜色，然后又被一种或多种不同的颜色覆盖涂色。

输入包含单个测试用例，格式如下。 $$ \begin{aligned} &n\ m\ x\ y \\ &c_1\ l_1\ r_1 \\ &\vdots \\ &c_m\ l_m\ r_m \end{aligned} $$ 其中，$n$ 是面板的数量（$1 \le n \le 10^9$），$m$ 是机器人的数量（$1 \le m \le 2 \times 10^5$）。$x$ 和 $y$ 是 $1$ 到 $10^5$ 之间（含）的整数。$x$ 是奖励值，$-y$ 是惩罚值。墙的面板按顺序编号为 $1$ 到 $n$。第 $i$ 个机器人被激活时，会将编号从 $l_i$ 到 $r_i$ 的所有面板（$1 \le l_i \le r_i \le n$）涂上颜色编号为 $c_i$ 的颜色（$c_i \in \{1,2,3\}$）。颜色编号 $1$、$2$ 和 $3$ 分别对应红色、绿色和蓝色。

输出一行一个整数，表示墙面可达到的最大美学价值。