You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时间限制：$1s$，空间限制：$512MB$

题目描述

​ 有一座高$n$层的楼房，里面有一架电梯，电梯初始时停在第$s$层，电梯每秒至多可以走$k$层，即第一秒可以走到$[s-k,s+k]$中的任意一层。

​ 现在有$m$个用户对电梯有需求，第$i$个用户会在第$t_i$秒，第$a_i$层按下电梯，此时若电梯和该用户处在同一层，则该用户会直接乘坐电梯（不考虑该用户进入电梯后对电梯运行的影响）；否则若当前电梯停在第x层，该用户的满意度会下降$|a_i-x|*b_i$，然后放弃乘坐电梯而去走楼梯。

​ 小Y希望用户的满意度尽可能的高，所以希望你求出用户满意度的和最少会下降多少。

输入格式

​ 输入文件名为$elevator.in$。

​ 输入文件的第一行包含$4$个正整数$n,m,s,k$，表示楼高n层，有m个用户需求，电梯初始在s层，每秒至多可以走k层。

​ 接下来的$m$行每行包含$3$个正整数$t_i,a_i,b_i$，表示用户会在第$t_i$秒，第$a_i$层按下电梯，满意度下降系数为$b_i$。

输出格式

​ 输出文件名的$elevator.out$。

​ 输出一个正整数表示满意度之和下降的最小值。

样例

样例1

输入数据：

4 2 1 1
1 3 5
2 4 8

输出数据：

13

数据范围与约定

对于$20\%$的数据，满足$n\le 5,\ k\le m\le 5,\ t_i\le 5$。

对于$40\%$的数据，满足$n\le 500,\ k\le m\le 500,\ t_i\le 500$。

对于$60\%$的数据，满足$n\le 500,\ k\le m\le 500$。

对于$100\%$的数据，满足$1\le n\le 5000,\ 1\le k\le m\le 5000,\ t_i\le 10^9,\ 1\le b_i\le 10^9$。