题目描述

爱丽丝要开车去上班，上班的路上有许多红绿灯，这让爱丽丝很难过。为了上班不迟到，她给自己的车安装了氮气喷射装置。现在她想知道自己上班最短需要多少时间。

爱丽丝的车最高速度是 $\frac{1}{V}$ 米每秒，并且经过改装后，可以瞬间加速到小于等于最高速的任意速度，也可以瞬间停止。

爱丽丝家离公司有 $N$ 米远，路上有 $M$ 个红绿灯，第 $i$ 个红绿灯位于离爱丽丝家 $A_i$ 米远的位置，绿灯持续 $B_i$ 秒，红灯持续 $C_i$ 秒。在初始时（爱丽丝开始计时的瞬间），所有红绿灯都恰好从红灯变为绿灯。如果爱丽丝在绿灯变红的瞬间到达红绿灯，她会停下车等红灯，因为她是遵纪守法的好市民。

氮气喷射装置可以让爱丽丝的车瞬间加速到超光速（且不受相对论效应的影响！），达到瞬移的效果，但是爱丽丝是遵纪守法的好市民，在每个红绿灯前她都会停下氮气喷射，即使是绿灯，因为红绿灯处有斑马线，而使用氮气喷射装置通过斑马线是违法的。此外，氮气喷射装置不能连续启动，需要一定时间的冷却，表现为通过 $K$ 个红绿灯后才能再次使用。（也就是说，如果 $K = 1$，就能一直使用啦！）初始时，氮气喷射装置处于可用状态。

输入格式

第一行四个正整数 $N$、$M$、$K$、$V$，含义如题面所述。

接下来 $M$ 行，每行三个正整数 $A_i$、$B_i$、$C_i$，含义如题面所述。

输出格式

输出一个正整数 $T$，表示爱丽丝到达公司最短需要多少秒。

90 2 2 2
30 20 20 
60 20 20

80

提示

【样例说明】

爱丽丝在最开始直接使用氮气喷射装置瞬间到达第一个红绿灯，然后绿灯通过，以最高速行进 $60$ 秒后到达第二个红绿灯，此时绿灯刚好变红，于是她等待 $20$ 秒再次变为绿灯后通过该红绿灯，此时氮气喷射装置冷却完毕，爱丽丝再次使用瞬间到达公司，总共用时 $80$ 秒。

【评测用例规模与约定】

对于 $30\%$ 的数据，$N \leq 100$；$M \leq 10$；$M < K$；$V = 1$.

对于 $60\%$ 的数据，$N \leq 1000$；$M \leq 100$；$K \leq 50$；$B_i, C_i \leq 100$；$V \leq 10$.

对于 $100\%$ 的数据，$0 < N \leq 10^3$；$M \leq 1000$；$K \leq 1000$；$0 < B_i, C_i \leq 10^6$；$0 < V \leq 10^6$；$0 < A_i < N$；对任意 $i < j$，有 $A_i < A_j$.