Description

这里有一面由若干垂直面板构成的墙。这些面板尚未涂色。

你拥有若干个机器人，每个机器人可以用单一颜色（红色、绿色或蓝色）为面板涂色。每个机器人被激活时，会在特定位置到另一个特定位置之间的面板上涂上特定颜色。每个机器人要涂色的面板和涂色颜色是固定的，但哪些机器人被激活以及它们的激活顺序可以任意决定。

你希望墙面被涂色后具有较高的美学价值。这里，墙面的美学价值简单地定义为墙面上所有面板的美学价值之和，而单个面板的美学价值定义如下：

• $0$，如果面板未被涂色。
• 指定的奖励值，如果面板只被涂上一种颜色，无论被涂了多少次。
• 指定的惩罚值（负值），如果面板先被涂上一种颜色，然后又被一种或多种不同的颜色覆盖涂色。

Input Format

输入包含单个测试用例，格式如下。

$$\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$ 分别对应红色、绿色和蓝色。

Output Format

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

8 5 10 5
1 1 7
3 1 2
1 5 6
3 1 4
3 6 8

70

26 3 9 7
1 11 13
3 1 11
3 18 26

182

21 10 10 5
1 10 21
3 4 16
1 1 7
3 11 21
3 1 16
3 3 3
2 1 17
3 5 18
1 7 11
2 3 14

210

21 15 8 7
2 12 21
2 1 2
3 6 13
2 13 17
1 11 19
3 3 5
1 12 13
3 2 2
1 12 15
1 5 17
1 2 3
1 1 9
1 8 12
3 8 9
3 2 9

153