Qaçış

Фibi eşitmişdi ki, fiziki məşqlər həm fiziki, həm də psixoloji sağlamlığa böyük təsir göstərir. O, əvvəllər heç vaxt yavaş-yavaş qaçmayıb və bunu sınamaq istəyir. Lakin o bilir ki, bu ona tezliklə darıxdırıcı gələcək, çünki eyni şeyi dəfələrlə etmək çətindir. Yavaş-yavaş qaçmağı vərdiş halına gətirmək üçün, Фibi bir çağırış qəbul etməyə qərar verdi: o, hər axşam maraqlı bir yol tapdığı müddətcə qaçışa çıxacaq. Onun üçün yol maraqlı hesab olunur, əgər o, əvvəllər heç vaxt qaçmadığı bir küçədən keçirsə. Фibi sizdən yaxşı planlaşdırarsa, maksimum neçə gün qaçışa çıxa biləcəyini anlamaqda kömək etməyinizi xahiş edir.

Фibi sizə öz məhəlləsinin təsvirini verir. O, bir kəsişmədə yaşayır və ətrafdakı bütün kəsişmələri təsvir edir. O, həmçinin hansı kəsişmələrin küçələrlə birləşdiyini və hər küçənin uzunluğunu metrlə bildirir. Hər küçə iki fərqli kəsişməni birləşdirir. Heç bir iki fərqli küçə eyni iki kəsişməni birləşdirmir. Bundan əlavə, Фibi yalnız evindən çatmaq mümkün olan küçələri təsvir etdiyini və küçələrin hər iki istiqamətdə keçilə biləcəyini fərz edə bilərsiniz, çünki Фibi piyada gedir.

Qaçış Фibinin evində başlayır və bitir və yolun uzunluğu Фibinin göstərdiyi diapazon daxilində olmalıdır. Фibi küçəyə çıxdıqda, bütün küçəni keçmək məcburiyyətində deyil (istənilən nöqtədə dönməyə icazə verilir), lakin bunu etsə belə, bu, qaçışların maraqlı olub-olmadığını müəyyən etmək üçün bütün küçəni gördüyü kimi hesab olunacaq. Qaçış maraqlı hesab olunur, əgər o, əvvəlki qaçışlarda görünməmiş bir küçəni (və ya onun bir hissəsini) əhatə edirsə. Kəsişməyə çatmaq, ona bitişik olan bütün küçələrin ziyarət edildiyi hesab olunmur.

Giriş verilənləri

Birinci sətir dörd tam ədəd $ISLU$ ehtiva edir. $I(1\le I\le 10^5)$ məhəllədəki kəsişmələrin sayını, $S(0\le S\le 10^5)$ küçələrin sayını təmsil edir. $L$ icazə verilən qaçışın minimum metr sayıdır, $U(1\le L\le U\le 42195$, Фibi marafon məsafəsindən çox qaçmayacaq) isə icazə verilən qaçışın maksimum metr sayıdır.

Sonra $S$ sətir gəlir, hər biri bir küçəyə uyğundur. Hər belə sətir $3$ tam ədəd $ijl$ ehtiva edir. $i$ və $j$ küçənin birləşdirdiyi kəsişmələrdir, $l(1\le l\le 1000)$ isə küçənin uzunluğudur. Kəsişmələr $0$-dan $I-1$-ə qədər nömrələnib, belə ki, Фibi $0$ nömrəli kəsişmədə yaşayır.

Çıxış verilənləri

Maksimum mümkün maraqlı qaçışların sayını ehtiva edən bir tam ədəd çıxarın.

Nümunələr

Qeyd

Birinci nümunə üçün maraqlı $3$ günlük qaçış planının nümunəsi:

• Birinci gün $0$ və $1$ arasında olan küçədə irəli-geri qaçın ($80$ metr).

• İkinci gün $2$-yə qədər küçədə $40$ metr qaçın, sonra eyni yolla geri dönün ($80$ metr).

• Üçüncü gün $1$-ə qədər küçədə qaçın, sonra $2$ istiqamətində $5$ metr qaçın, sonra eyni yolla geri dönün ($90$ metr).

Mümkün qaçışlardan biri: $0$-dan $1$-ə qaçın, sonra $0$-a geri dönün, sonra $1$ istiqamətində yarım metr qaçın və sonra $0$-a geri dönün.