벽 칠하기

벽은 세로로 긴 패널 여러 장으로 이루어져 있다. 패널은 아직 칠해지지 않은 상태이다.

로봇이 여러 대 있다. 각 로봇은 빨강, 초록, 파랑 중 한 가지 색으로 패널을 칠할 수 있다. 로봇을 실행하면 위치 $l$부터 위치 $r$까지의 패널을 그 로봇의 색으로 칠한다. 각 로봇이 칠하는 패널 범위와 색은 정해져 있지만, 어떤 로봇을 실행할지와 실행 순서는 자유롭게 정할 수 있다.

벽의 미적 가치는 패널들의 미적 가치를 모두 더한 값이다. 패널의 미적 가치는 다음과 같다.

• 칠해지지 않은 패널은 0이다.
• 몇 번을 칠했든 한 가지 색으로만 칠해진 패널은 보너스 값 $x$이다.
• 한 색으로 칠한 뒤 다른 색으로 한 번 이상 덧칠된 패널은 페널티 값 $-y$이다.

첫 줄에 $n$, $m$, $x$, $y$가 주어진다. $n$은 패널의 개수, $m$은 로봇의 개수, $x$는 보너스 값, $-y$는 페널티 값이다.

이어지는 $m$개의 줄에는 각각 $c_i$, $l_i$, $r_i$가 주어진다. 로봇 $i$는 패널 $l_i$부터 $r_i$까지를 색 $c_i$로 칠한다. 색 1은 빨강, 색 2는 초록, 색 3은 파랑이다.

n m x y
c1 l1 r1
.
.
.
cm lm rm

제약: $1 \le n \le 10^9$, $1 \le m \le 2 \times 10^5$, $1 \le x, y \le 10^5$, $c_i \in \{1, 2, 3\}$, $1 \le l_i \le r_i \le n$.

달성할 수 있는 벽의 최대 미적 가치를 한 줄에 정수 하나로 출력한다.