시간 이동

플랫란디아에는 $n$개의 도시가 있다. 플랫란디아는 지구에 있지 않으므로 하루는 $2s$시간이고, 1년은 $T$일, 즉 정확히 $2sT$시간이다.

플랫란디아의 각 도시에는 자체 정부가 있고, 각 도시마다 시간 이동에 관한 법률이 다르다. 일부 도시에서는 여름 시간과 겨울 시간뿐 아니라 봄, 가을, 간절기, 축제일, 휴일 시간까지 있다. 도시마다 법이 다르므로 서로 다른 도시의 시간이 크게 차이 나는 일이 자주 발생한다. 당연히 많은 종류의 시간이 존재하면 주민들이 불편을 겪는다.

번호 $n$인 도시는 플랫란디아의 수도이다. 다른 나라와의 소통을 위해 이 도시에서는 시간을 절대 바꾸지 않는다. 또한 다른 모든 도시와 수도 사이의 시간 차이는 절댓값으로 $s$시간을 넘지 않는다.

시간을 측정하고 시계를 조정하는 과정을 설명하자. 각 도시의 중심에는 거대한 시계가 있다. 이 시계는 그 도시의 현재 날짜 번호와 현재 시간을 표시한다. 분과 초는 표시하지 않는데, 정부가 중요하지 않다고 여기기 때문이다. 해마다 옛 전통에 따라 모든 도시의 시간이 동기화되고, 각 도시의 새해는 자정, 즉 모든 시계가 0을 가리키는 상태에서 첫째 날이 시작된다. 도시에서 자정이 될 때마다 새로운 날이 시작되어 그 도시의 현재 날짜 번호가 바뀐다. 도시에 시간 이동일이 오면 그날 정오(시계가 $s$시간을 가리킬 때)가 처음 되었을 때 법에 정해진 값만큼 시계를 이동한다. 이동은 현재 날짜 번호를 바꾸지 않지만, $s$시간 앞으로 이동하면 곧바로 자정이 되어 그 도시의 다음 날이 시작된다.

플랫란디아 불편 평가 특별 위원회는 불편을 수치로 나타내는 지표를 만들었다. 나라의 시간 불편은 어느 한 시간 동안 모든 도시 쌍의 시간 차이 절댓값의 합이다. 즉, $i$번 도시의 현재 날짜 번호를 $d_i$, 현재 시간을 $c_i$라 할 때 $t_i = 2sd_i + c_i$로 두자. 서로 다른 도시의 순서 없는 쌍 $\{i, j\}$ 모두에 대해 $|t_i - t_j|$를 합한 값이 나라의 시간 불편이다. 연간 불편은 해가 시작된 뒤 $2sT$시간 동안의 시간 불편을 모두 더한 값이다.

한 해 동안 각 도시의 시간 이동 일정이 주어진다. 연간 불편을 계산하는 것이 과제이다. 해가 시작될 때 모든 도시의 시간은 같고 자정, 즉 시계가 0인 상태에서 시작한다. 어느 도시든 시간 이동은 현지 시각 정오, 즉 $s$시간에만 일어난다. 해가 시작될 때의 시계 동기화는 큰 문화 행사로 모든 도시에서 동시에 일어나므로 입력에 주어지지 않는다.

첫째 줄에는 네 정수 $n$, $m$, $s$, $T$가 주어진다. ($2 \le n \le 10^4$; $1 \le m \le 10^5$; $1 \le s \le 10^4$; $1 \le T \le 100$) 다음 $m$개 줄에는 시간 이동이 주어진다. 각 줄은 세 수 $d_i$, $k_i$, $t_i$로 이루어진다. $d_i$는 시간 이동이 일어나는 날짜 번호, $k_i$는 시간 이동이 일어나는 도시 번호, $t_i$는 시간을 이동하는 시간 수이다. ($1 \le d_i$; $1 \le k_i \le n - 1$; $-s \le t_i \le s$; $t_i \ne 0$) 각 이동은 200시간을 넘지 않는다.

입력 데이터는 올바른 것으로 보장된다. 각 도시에서 하루에 일어나는 이동은 최대 하나이다. 플랫란디아 사람들은 날짜를 1부터 센다.

연간 불편을 나타내는 정수 하나를 출력한다. 답은 $8 \cdot 10^{18}$을 넘지 않는 것으로 보장된다.