有一面由若干垂直面板组成的墙。这些面板尚未上色。

你拥有若干机器人，每个机器人可以将面板涂成红色、绿色或蓝色中的一种颜色。每个机器人在被激活时，会将特定范围内的面板涂成特定的颜色。每个机器人所覆盖的面板范围和涂色种类是固定的，但你可以决定激活哪些机器人以及它们的激活顺序。

你希望墙壁的涂色具有较高的美学价值。墙壁的美学价值定义为所有面板美学价值的总和，而单个面板的美学价值定义如下：

• 如果面板未被涂色，则为 $0$。
• 如果面板仅被涂成一种颜色（无论被涂了多少次），则为指定的奖励值。
• 如果面板先被涂成某种颜色，随后又被涂成一种或多种不同的颜色，则为指定的惩罚值。

输入格式

输入的第一行包含四个整数 $n, m, x$ 和 $y$。$n$ 是面板的数量 ($1 \le n \le 10^9$)，$m$ 是机器人的数量 ($1 \le m \le 2 \cdot 10^5$)。$x$ 和 $y$ 是 $1$ 到 $10^5$ 之间的整数（包含边界）。$x$ 为奖励值，$-y$ 为惩罚值。墙上的面板从 $1$ 到 $n$ 依次编号。

接下来的 $m$ 行，每行描述一个机器人。第 $i$ 行包含三个整数 $c_i, l_i$ 和 $r_i$，表示第 $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$ 分别对应红色、绿色和蓝色。

输出格式

输出一行，包含一个整数，表示墙壁所能达到的最大美学价值。

样例

样例输入 1

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

样例输出 1

70

样例输入 2

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

样例输出 2

182

样例输入 3

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

样例输出 3

210

样例输入 4

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

样例输出 4

153