Pheobe 听说锻炼对身心健康都有巨大的影响。她以前从未慢跑过，并想尝试一下。然而，她知道自己很容易感到厌倦，而且很难坚持重复做同一件事。为了养成慢跑的习惯，Pheobe 决定接受一个挑战：只要能找到一条有趣的路径，她每天晚上都会出去跑步。对她来说，如果一条路径经过了她以前从未跑过的街道，那么这条路径就是有趣的。Pheobe 请求你帮助她计算，如果规划得当，她最多可以坚持跑步多少天。

Pheobe 给你输入了她所在社区的描述。她住在某个路口，并描述了社区中所有的路口。她还告诉你哪些路口由街道连接，以及每条街道的长度（以米为单位）。每条街道连接两个不同的路口，且不可能有两条不同的街道连接相同的两个路口。此外，你可以假设 Pheobe 描述的街道都是从她家可以到达的，并且由于 Pheobe 是步行，街道可以双向通行。

一次有效的跑步从 Pheobe 的家出发并回到家，其长度应在 Pheobe 指定的范围内。当 Pheobe 进入一条街道时，她不必跑完全程（她可以在任何一点折返），但即使她这样做，为了判断跑步是否有趣，这也算作她已经“见过”了整条街道。如果一次跑步包含了一条在之前的跑步中未曾出现的街道（或其一部分），则该次跑步被认为是“有趣”的。到达一个路口并不算作访问了所有与该路口相邻的街道。

输入格式

输入的第一行包含四个空格分隔的整数 $I, S, L, U$。$I$ 表示社区中的路口数量，$S$ 表示街道数量。$L$ 是有效跑步的最小米数，$U$ 是有效跑步的最大米数。

接下来 $S$ 行，每行代表一条街道。每行包含 3 个空格分隔的整数 $i, j, \ell$，其中 $i$ 和 $j$ 是街道连接的路口，$ \ell $ 是街道的长度（以米为单位）。路口编号为 $0$ 到 $I - 1$，Pheobe 住在编号为 $0$ 的路口。

输出格式

输出一行，包含一个整数，表示最长的有趣跑步序列的长度（天数）。

数据范围

• $1 \le I \le 100\,000$
• $0 \le S \le 100\,000$
• $1 \le L \le U \le 42\,195$（Pheobe 跑步距离不会超过一场马拉松）
• $1 \le \ell \le 1\,000$

样例

样例输入 1

4 4 80 90
0 1 40
0 2 50
1 2 30
2 3 10

样例输出 1

3

说明 1

这是一个针对第一个样例输入的有趣 3 天慢跑计划示例： 第一天，在连接 0 和 1 的街道上来回跑（80 米）。 第二天，在通往 2 的街道上跑 40 米，然后沿原路返回（80 米）。 * 第三天，在通往 1 的街道上跑，然后向 2 的方向跑 5 米，再沿原路返回（90 米）。

样例输入 2

2 1 7 7
0 1 3

样例输出 2

1

说明 2

这是一个可能的有效跑步示例：从 0 跑到 1，然后回到 0，接着向 1 的方向跑 0.5 米，然后回到 0。