CF1776E Crossing the Railways

Isona 在一个火车站里。这个站有两个站台，在它们之间有 $m$ 条平行铁轨，可以看作是无限长的直线。每条铁轨用从 $1$ 到 $m$ 进行编号，铁轨 $1$ 是最靠近第一个站台的，而铁轨 $m$ 则是最远的。相邻铁轨之间有 $1$ 米的距离，每个站台与最靠近它的铁轨之间也是如此。 Isona 站在第一个站台的内边界，突然她意识到自己忘记验票了！第二个站台上有一台验票机，正好位于她当前位置的对面（因此，伊索娜与验票机之间的距离是 $m+1$ 米）。只剩下 $s$ 秒来验票，而用于横越铁轨的桥离验票机太远了。因此，Isona（非常勇敢但有点粗心）将沿与铁轨垂直的方向来横穿铁轨。Isona 只能向前奔跑（不能后退），也可以原地停留。当她以最高速度奔跑时，她需要 $v$ 秒来穿越 $1$ 米。她可以以小于或等于她的最大速度奔跑。 只不过存在一个问题：有 $n$ 列火车被安排在这些铁轨上行驶。第 $i$ 列火车将行驶在铁轨 $r_i$ 。它们将从现在开始 $a_i$ 秒后开始横穿 Isona 和验票机之间的直线，结束于 $b_i$ 秒后。当然，在火车通过时，Isona 不能横穿铁轨。形式上，对于每一个 $i=1,2,...,n$，在任何时间 $t$ 满足 $a_i

输入的第一行包含四个整数 $n$，$m$，$s$，$v$ $(1 \le n \le 500,1 \le m \le 10,1 \le s,v \le 10^9)$，分别表示火车的数量，铁路的数量，伊索娜过铁路的最长时间（以秒为单位），以及她以最大速度穿过 $1$ 米所需的秒数。 接下来的 $n$ 行中，每行包含三个整数 $a_i,b_i,r_i$ $(1 \le a_i < b_i \le 10^9,1 \le r_i \le m)$，分别表示第 $i$ 列车横穿 Isona 和验证机之间的直线开始和结束的时间，以及它行驶在哪条铁路上。 保证对于任意两列列车 $i$ 和 $j$，它们通过相同的铁路（即 $r_i=r_j$）时，它们之间至少有 $1$ 秒的间隔（即 $a_i\ge b_j+1$ 或 $a_j\ge b_i+1$）。也就是说，不会撞车。

输出 Isona 为了准时到达验证机所需要进行的最少变速次数。如果不可能在限制时间内到达的，则输出 $-1$。 ### **说明/提示** 在样例一中，如果 Isona 在时间 $t=0$ 以最大速度 $(1m/s)$ 开始奔跑，她将恰好在每列火车即将穿过铁路时穿过铁路，而且她将在时间 $s-1=4$ 结束时到达另一个站台，不需要改变速度。所以输出为 $0$。 在样例二中，一个可能的解决方案是进行 $2$ 次速度更改，具体操作如下：前 $2$ 秒，Isona 以最大速度 $(0.5m/s)$ 奔跑，然后在接下来的 $4$ 秒内减速到 $0.25m/s$ (答案 $+1$)，直到她到达第二条铁路。在那里上，她再次以最大速度奔跑（答案 $+1$），直到到达另一个站台。 在样例三中，Isona 可以等待 $2$ 秒后开始奔跑。然后她以最大速度$(0.5m/s)$ 奔跑了 $5$ 秒。之后，她停下来等待 $1$ 秒不奔跑（或以 $0m/s$ 的速度奔跑），最后在最后 $5$ 秒以最大速度再次奔跑。总体而言，她更改了 $2$ 次速度。 在样例四中，Isona 最快也就是一开始便以最大速度 $(0.5m/s)$ 奔跑，刚好 $2$ 秒时到达铁轨 $1$，此时火车恰好驶过。但是由于没有剩余时间了，所以直接输出 $-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.