CF1776E.Crossing the Railways

Isona is in a train station. This station has two platforms, and between them there are $m$ parallel railways that can be viewed as infinite straight lines. Each railway is identified with an integer from $1$ to $m$, railway $1$ being the closest to the first platform and railway $m$ being the farthest. There is a $1$ meter distance between consecutive railways, as well as between each platform and its closest railway.

Isona is standing on the inner border of the first platform, when she realizes that she forgot to validate her ticket! There is a validating machine on the second platform, exactly opposite her current position (thus, the distance between Isona and the validating machine is $m + 1$ meters). There are only $s$ seconds left to validate the ticket and the bridge designated to cross the railways is too far from the validating machine. Therefore, Isona (who is very brave and a little bit careless) will cross the railways running in a straight line perpendicular to the railways themselves. Isona can only run forward (not backward) and she can stay still. When she runs at maximum speed, she needs $v$ seconds to traverse $1$ meter. She can run at any speed less than or equal to her maximum speed.

There is only one problem: $n$ trains are programmed to transit through the railways. The $i$-th train will use the railway $r_i$. It will start crossing the straight line between Isona and the validating machine $a_i$ seconds from now and it will end $b_i$ seconds from now. Of course, Isona cannot cross a railway when a train is passing. Formally, for every $i = 1, \, 2, \, \dots, \, n$, Isona is not allowed to be on railway $r_i$ at any time $t$ with $a_i \lt t \lt b_i$ (but she is allowed to cross at times $a_i$ or $b_i$).

The following picture summarizes the situation. In the picture there are $m = 4$ railways and two trains are visible; the train going through railway $3$ is currently crossing the line between Isona and the validating machine.

Isona is a really good runner, but she gets tired every time she has to change her running speed. What is the minimum number of speed changes she has to perform to get to the validating machine on the other platform within $s$ seconds from now? Note that at the beginning Isona is not running. She can start to run anytime. The instant she starts to run (i.e. her speed becomes positive) is not counted as a speed change.

伊索娜正在一座火车站内。该车站有两座站台，其间有 $m$ 条彼此平行的铁路线，可视为无限长的直线。每条铁路线用一个从 $1$ 到 $m$ 的整数标识：铁路 $1$ 距离第一座站台最近，铁路 $m$ 距离第二座站台最近。相邻两条铁路线之间的距离为 $1$ 米；每座站台与其邻近的铁路线之间也相距 $1$ 米。

伊索娜正站在第一座站台的内侧边缘，此时她突然意识到自己忘记验票了！第二座站台上恰好正对着她当前位置的位置设有一台验票机（因此，伊索娜与验票机之间的距离为 $m + 1$ 米）。距离验票截止仅剩 $s$ 秒，而专供横跨铁路线的人行天桥离验票机太远。因此，伊索娜（她非常勇敢，又略有些粗心）决定以垂直于所有铁路线的方向沿一条直线奔跑穿过这些铁路线。伊索娜只能向前跑（不能后退），也可以静止不动。当她以最大速度奔跑时，穿越 $1$ 米需要 $v$ 秒；她可以以任意不超过其最大速度的速度奔跑。

但存在唯一一个问题：共有 $n$ 列火车按计划驶过这些铁路线。第 $i$ 列火车将驶经铁路线 $r_i$，它将在当前时刻起 $a_i$ 秒后开始穿越伊索娜与验票机之间的连线，并于当前时刻起 $b_i$ 秒后结束穿越。显然，伊索娜在列车经过时不得穿越对应铁路线。形式化地说，对每个 $i = 1,\,2,\,\dots,\,n$，伊索娜在任意时刻 $t$ 满足 $a_i < t < b_i$ 时均不可位于铁路线 $r_i$ 上（但在时刻 $a_i$ 或 $b_i$ 穿越是允许的）。

下图概括了该场景。图中显示 $m = 4$ 条铁路线，且可见两列火车；其中一列正行驶在铁路线 $3$ 上，此刻正穿越伊索娜与验票机之间的连线。

伊索娜是一位出色的跑者，但每次改变奔跑速度都会令她感到疲惫。那么，在当前起 $s$ 秒内成功抵达对岸站台上的验票机，她最少需要改变多少次速度？注意：初始时刻伊索娜处于静止状态，她可以在任意时刻开始奔跑；她开始奔跑的瞬间（即速度由零变为正值）不计为一次速度变化。

The first line of the input contains four integers $n$, $m$, $s$, $v$ ($1 \leq n \leq 500$, $1 \leq m \leq 10$, $1 \leq s, v \leq 10^9$) — the number of trains, the number of railways, the maximum time in seconds Isona can spend crossing the railways, and the number of seconds she needs to traverse $1$ meter at maximum speed.

Each of the next $n$ lines contains three integers $a_i$, $b_i$, $r_i$ ($1 \leq a_i \lt b_i \leq 10^9$, $1 \leq r_i \leq m$) — the start and end times of the $i$-th train crossing the straight line between Isona and the validating machine, and the railway it will be using.

It is guaranteed that, for any two trains $i$ and $j$ that go through the same railway (i.e. $r_i = r_j$), there is at least $1$ second between them (that is, either $a_j \ge b_i + 1$ or $a_i \ge b_j + 1$).

输入的第一行包含四个整数 $n$、$m$、$s$、$v$（$1 \leq n \leq 500$，$1 \leq m \leq 10$，$1 \leq s, v \leq 10^9$）——分别表示列车数量、铁路数量、Isona 穿越铁路所能花费的最大时间（单位：秒），以及她以最大速度行走 $1$ 米所需的时间（单位：秒）。

接下来的 $n$ 行中，每行包含三个整数 $a_i$、$b_i$、$r_i$（$1 \leq a_i \lt b_i \leq 10^9$，$1 \leq r_i \leq m$）——分别表示第 $i$ 列车穿越 Isona 与验证机之间直线段的起始时刻和结束时刻，以及该列车所使用的铁路编号。

保证：对任意两条经过同一条铁路的列车 $i$ 和 $j$（即 $r_i = r_j$），它们的时间区间至少相隔 $1$ 秒（即满足 $a_j \ge b_i + 1$ 或 $a_i \ge b_j + 1$）。

Print the minimum number of speed changes Isona has to perform to get to the validating machine in time. If this is impossible, print $-1$.

输出 Isona 为及时到达验证机所需的最小速度变化次数。若无法实现，则输出 $-1$。

In the first sample, if Isona starts running at time $t=0$ at maximum speed ($1$ m/s), she will cross each railway just when a train is about to traverse it, and she will arrive at the other platform at time $4 = s - 1$ without changing speed.

In the second sample, a possible solution with $2$ speed changes is the following: for the first $2$ seconds Isona goes at maximum speed ($0.5$ m/s), then she slows down to $0.25$ m/s for $4$ seconds until she reaches the second railway. At that point, she goes at maximum speed again until she reaches the other platform.

In the third sample, Isona can wait $2$ seconds before starting running. She then runs for $5$ seconds at maximum speed ($0.5$ m/s). After that, she waits for $1$ second not running (or running at $0$ m/s), and finally she runs again at maximum speed for the last $5$ seconds. Overall, she changes speed twice.

在第一个样例中，如果伊索娜在 $t=0$ 时刻以最大速度（$1$ m/s）起跑，她将在每列火车即将通过各铁路道口的时刻恰好穿越它们，并以恒定速度抵达对面站台，到达时间为 $4 = s - 1$。

在第二个样例中，一种需进行 $2$ 次变速的可行方案如下：前 $2$ 秒伊索娜以最大速度（$0.5$ m/s）奔跑；随后将速度降至 $0.25$ m/s 并持续 $4$ 秒，直至抵达第二处铁路道口；此时她再次以最大速度奔跑，直至抵达对面站台。

在第三个样例中，伊索娜可先静止等待 $2$ 秒再起跑；接着以最大速度（$0.5$ m/s）奔跑 $5$ 秒；之后静止等待 $1$ 秒（或以 $0$ m/s 的速度“奔跑”）；最后再以最大速度奔跑最后 $5$ 秒。整个过程中，她共改变速度两次。