该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

$17$ 级台风马上就要来了！政府下达了一级抗台预警！

在逃离的过程中，徐老师发现有一座摇摇欲坠的大桥！

在这个大桥上有 $n$ 辆汽车正在行驶，由于桥上的车道是单行车道，只够一辆车通行，所以这 $n$ 辆车只能排成一列依次通过大桥，就算后车的速度赶上了前车也不能超车，只能减速到前车的速度行驶。

形式化的来说大桥可以看成一条数轴，末尾的位置为 $T$，其中第 $i$ 辆车的车头位置为 $r_i$，车尾位置为 $l_i$，行驶速度为 $v_i$，这辆车在数轴上覆盖的区域就是 $(l_i, r_i]$。

特别的，所有车一直都是匀速前行，过了终点也不例外。

台风马上就要到了！徐老师决定拿出自己珍藏的 $m$ 个加速器分发给这些车主，每个加速器可以让一台汽车的速度增加 $k$，徐老师需要合理的分配这些加速器，使得所有汽车尽快逃离大桥！

P.S.1 这里你可以认为徐老师分发加速器不需要时间，可以在瞬间完成汽车加速 P.S.2 当最后一辆汽车的车尾离开大桥的范围，即 $l_{last} >= T$，才算完全逃离大桥 P.S.3 同一台汽车可以使用多个加速器

输入格式

输入第一行包含四个整数 $n,T,m,k$，含义如题

接下来 $n$ 行，每行包含三个整数 $l_i,r_i,v_i$ 描述一辆车的状态

特别的，题目保证不会出现两辆车重叠，但可能会有一台车的 $r$ 和另一台车的 $l$ 相同，这依旧符合 不重叠 的描述

输出格式

输出一个小数，表示最小逃离时间，输出保留 $3$ 位小数

数据范围

对于全部测试点满足： $1 \leq n \leq 3 \times 10^5, 0 \leq m \leq 3 \times 10^5$, $0 \leq l_i \leq r_i \leq T \leq 10^9$, $1 \leq k, v_i \leq 3000$。

样例输入1

3 20 2 3
10 15 1
1 1 4
4 7 9

样例输出1

3.250

样例解释

将两个加速器分别用到第一辆车和第二辆车

第一辆车的速度变为 $4$，第二辆车的速度变为 $7$

• 阶段 $1 (0 \sim 0.6s)$：车 $3$（中，$v=9$）追赶车 $1$（前，$v=4$）

车 $3$ 车头从 $7$ 出发，车 $1$ 车尾从 $10$ 出发，速度差 $9-4=5$，间隙 $3$，追及时间 $3/5 = 0.6s$。

此时车 $3$ 车头到达 $7 + 9 \times 0.6 = 12.4$ 跟车 $1$ 邻接在一起 ，随后减速至 $v=4$

此时三辆车的状态分别为

12.4 17.4 4
5.2 5.2 7
9.4 12.4 4

• 阶段 $2 (0.6 \sim 2.0s)$：车 $2$（后，$v=7$）追赶车 $3$（中，现 $v=4$）

同上，车 $2$ 和 车 $3$ 速度差位 $7-4=3$，间隙 $9.4-5.2=4.2$，追及时间$4.2/3=1.4s$

此时车 $2$ 的车头到达 $5.2+1.4 * 7=15$，跟车 $3$ 邻接在一起，随后减速至 $v=4$

此时三辆车的状态分别为

18 23 4
15 15 4
15 18 4

• 阶段 $3(2.0 \sim 3.25s)$：

直到车 $2$ 离开需要时间 $(20-15)/4=1.25s$ 此时车 $2$ 的车尾到达 $15+1.25 * 4=20$ 刚好离开大桥，一共花费时间 $2+1.25=3.25s$