Бег трусцой

Фиби слышала, что физические упражнения оказывают огромное влияние как на физическое, так и на психическое здоровье. Она никогда раньше не бегала трусцой и хочет попробовать. Однако она знает, что ей это быстро надоест, так как сложно многократно делать одно и то же. Чтобы выработать привычку бегать трусцой, Фиби решила принять вызов: она будет выходить на пробежку каждый вечер, пока находит интересный путь. Для нее путь считается интересным, если он проходит по улице, по которой она никогда раньше не бегала. Фиби просит Вас помочь понять, какое максимальное количество дней она сможет выходить на пробежку, если хорошо ее спланирует.

Фиби дает Вам описание своего района. Она живет на перекрестке и описывает все перекрестки по соседству. Она также сообщает Вам, какие перекрестки соединены улицами, и какова длина каждой улицы в метрах. Каждая улица соединяет два разных перекрестка. Никакие две разные улицы не соединяют одни и те же два перекрестка. Кроме того, Вы можете предположить, что Фиби описывает только те улицы, до которых можно добраться из своего дома, и что улицы можно пройти в обоих направлениях, поскольку Фиби ходит пешком.

Пробежка начинается и заканчивается в доме Фиби, и длина пути должна быть в пределах диапазона, указанного Фиби. Когда Фиби выходит на улицу, она не обязана проходить через всю улицу (ей разрешено развернуться в любой точке), но даже если она это сделает, это будет считаться, как если бы она увидела всю улицу для целей определения интересны ли пробежки. Пробег считается интересным, если он включает в себя улицу (или ее отрезок), которая не появлялась в предыдущих пробежках. Достижение перекрестка не считается посещением всех прилегающих к нему улиц.

Входные данные

Начинается с одной строки, содержащей четыре целых числа $ISLU$. $I(1\le I\le 10^5)$ представляет количество перекрестков в окрестности, а $S(0\le S\le 10^5)$ представляет количество улиц. $L$ — минимальное количество метров в допустимом пробеге, а $U(1\le L\le U\le 42195$, Фиби не будет бежать больше чем марафонская дистанция) — это максимальное количество метров в допустимом пробеге.

Затем следует $S$ строк, каждая из которых соответствует улице. Каждая такая строка содержит $3$ целых числа $ijl$. $i$ и $j$ — это перекрестки, которые соединяет улица, а $l(1\le l\le 1000)$ — длина улицы в метрах. Перекрестки пронумерованы от $0$ до $I-1$, так что Фиби живет на перекрестке с номером $0$.

Выходные данные

Выведите одно целое число, содержащее наибольшее возможное количество интересных пробежек.

Примеры

Примечание

Вот пример интересного $3$-дневного плана пробежек для первого примера:

• В первый день бегайте туда-сюда по улице между $0$ и $1(80$ метров).

• Во второй день пробежать $40$ метров по улице до $2$, после чего вернуться тем же путем ($80$ метров).

• На третий день бегите по улице до $1$, затем пробегите $5$ метров в направлении $2$, затем вернитесь назад тем же путем ($90$ метров).

Вот одна из возможных пробежек: бегите от $0$ к $1$, затем обратно к $0$, затем полметра в направлении $1$, а затем обратно к $0$.