Isona 正在火车站。车站有两个站台，中间有 $m$ 条平行的铁轨，可以看作无限长的直线。每条铁轨用从 $1$ 到 $m$ 的整数标识，铁轨 $1$ 离第一个站台最近，铁轨 $m$ 最远。相邻铁轨之间以及每个站台与其最近的铁轨之间都有 $1$ 米的距离。

Isona 站在第一个站台的内侧边缘，这时她意识到自己忘了检票！在第二个站台上，正对着她当前位置的地方有一个检票机（因此，Isona 和检票机之间的距离是 $m+1$ 米）。距离检票机还有 $s$ 秒的时间，而指定的跨越铁轨的桥梁离检票机太远了。因此，Isona（她非常勇敢但有点粗心）将沿着垂直于铁轨的直线跑过去跨越铁轨。Isona 只能向前跑（不能后退），也可以保持静止。当她以最大速度奔跑时，她需要 $v$ 秒跑完 $1$ 米。她可以以小于或等于最大速度的任意速度奔跑。

这里只有一个问题：有 $n$ 列火车计划通过这些铁轨。第 $i$ 列火车将使用铁轨 $r_i$。它将在 $a_i$ 秒后开始穿过 Isona 和检票机之间的直线，并在 $b_i$ 秒后结束。当然，Isona 不能在火车经过时穿过铁轨。形式化地说，对于每个 $i = 1, 2, \dots, n$，Isona 不允许在任何时间 $t$（满足 $a_i < t < b_i$）处于铁轨 $r_i$ 上（但她可以在时间 $a_i$ 或 $b_i$ 时穿过）。

下图总结了这种情况。图中共有 $m=4$ 条铁轨，可以看到两列火车；正在通过铁轨 $3$ 的火车目前正穿过 Isona 和检票机之间的直线。

Isona 是一个很棒的跑步者，但每次改变奔跑速度时她都会感到疲劳。为了在 $s$ 秒内到达另一个站台的检票机，她最少需要进行多少次速度改变？注意，开始时 Isona 没有在跑。她可以随时开始跑。她开始跑的那一刻（即她的速度变为正值）不计为一次速度改变。

输入格式

第一行包含四个整数 $n, m, s, v$ ($1 \le n \le 500, 1 \le m \le 10, 1 \le s, v \le 10^9$)，分别表示火车数量、铁轨数量、Isona 跨越铁轨所能花费的最大时间（秒），以及她以最大速度跑完 $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_j \ge b_i + 1$ 或 $a_i \ge b_j + 1$）。

输出格式

输出 Isona 为了准时到达检票机所需的最少速度改变次数。如果不可能，输出 $-1$。

样例

样例输入 1

4 3 5 1
1 2 1
3 4 1
2 3 2
3 4 3

样例输出 1

0

说明 1

如果 Isona 在 $t=0$ 时以最大速度（$1$ 米/秒）开始奔跑，她将在火车即将穿过铁轨时刚好穿过每条铁轨，并且她将在时间 $4 = s - 1$ 时到达另一个站台，而无需改变速度。

样例输入 2

3 3 12 2
2 10 1
1 6 2
8 12 3

样例输出 2

2

说明 2

一种可能的 $2$ 次速度改变的方案如下：前 $2$ 秒 Isona 以最大速度（$0.5$ 米/秒）奔跑，然后她减速到 $0.25$ 米/秒持续 $4$ 秒，直到她到达第二条铁轨。在那一点，她再次以最大速度奔跑，直到她到达另一个站台。

样例输入 3

8 4 13 2
1 4 1
5 13 1
1 5 2
6 13 2
1 9 3
10 13 3
1 10 4
11 13 4

样例输出 3

2

说明 3

Isona 可以等待 $2$ 秒后再开始奔跑。然后她以最大速度（$0.5$ 米/秒）奔跑 $5$ 秒。之后，她等待 $1$ 秒不奔跑（或以 $0$ 米/秒的速度奔跑），最后她再次以最大速度奔跑最后 $5$ 秒。总共，她改变了两次速度。

样例输入 4

1 1 2 2
1 2 1

样例输出 4

-1