问题描述

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

爱丽丝的车最高速度是 $\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^8 ; 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$.