Problem description

Jasio zdał właśnie egzamin na prawo jazdy. Wybiera się na pierwszą przejażdżkę – pojedzie do dziewczyny na spotkanie. Z uwagi, że nie czuje się na drodze jeszcze zbyt pewnie, postanowił że pojedzie na wprost przed siebie. Problem w tym, że nawet jazda na wprost nie jest taka trywialna jak by mogło się wydawać. Na drodze jest bowiem kilka sygnalizacji świetlnych, które czasami wymuszają zatrzymanie się (gdy świeci się czerwone światło).

Jasio uwielbia jeździć na tempomacie. Niestety, nie dorobił się jeszcze auta wyposażonego w aktywny tempomat z hamowaniem, dlatego musi zadowolić się jazdą ze stałą prędkością. Postanowił przejechać całą trasę z równą prędkością. Dzięki temu oszczędzi trochę paliwa i ochroni cenne roślinki, a także przyczyni się do zmniejszenia problemu smogu.

Zanim wyruszył, dokładnie przeanalizował, w których punktach na trasie znajdują się sygnalizacje i jakie są na nich ustawione cykle świateł. Chciałby przejechać trasę ze stałą (najchętniej największą możliwą) prędkością, ale z drugiej strony nie chciałby tak od razu stracić prawa jazdy – tzn. chciałby możliwie mało razy przejechać na czerwonym świetle.

Są oczywiście pewne naturalne ograniczenia – samochód Jasia nie pojedzie szybciej niż V metrów na sekundę, zaś z drugiej strony – Jasio nie chce się spóźnić do dziewczyny, więc postanowił, że interesuje go tylko pokonanie trasy w co najwyżej T sekund.

Napisz program, który wczyta opis trasy Jasia (pozycje sygnalizatorów oraz opis cykli świateł panujących na nich), wyznaczy minimalną liczbę przejazdów na czerwonym świetle potrzebnych do przejechania trasy ze stałą prędkością, zgodnie z ograniczeniami Jasia i wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się cztery liczby naturalne: N, L, V oraz T, pooddzielane pojedynczymi odstępami i określające kolejno liczbę sygnalizatorów na trasie Jasia, długość trasy w metrach, maksymalną prędkość pojazdu Jasia oraz maksymalny czas jaki Jasio daje sobie na przejazd. W kolejnych N wierszach znajduje się opis sygnalizatorów. Opis każdego z nich składa się z czterech liczb naturalnych: p_i, q_i, s_i, e_i, pooddzielanych pojedynczymi odstępami i określających, że sygnalizator znajduje się na p_i-tym metrze trasy oraz światło zielone wyświetlane jest w sekundach [k⋅q_i+s_i,k⋅q_i+e_i] dla dowolnego naturalnego k.

Pozycje sygnalizatorów są parami różne.

Wyjście

W pierwszym (i jedynym) wierszu wyjścia powinna się znaleźć jedna liczba naturalna – minimalna liczba przejazdów na czerwonym świetle niezbędna do przejechania trasy ze stałą prędkością.

Jeśli pokonanie trasy przy założeniach Jasia jest w ogóle niemożliwe – zamiast tego należy wypisać tylko jedno słowo NIE.

Uwaga

Jasio rozpoczyna podróż w sekundzie numer 0.

Należy założyć, że jeśli Jasio przejedzie obok sygnalizatora dokładnie w momencie zmiany świateł to przejeżdża zgodnie z przepisami (choć na krawędzi).

Ograniczenia

1 ≤ N ≤ 500, 1 ≤ V ≤ 5 000, 2 ≤ T ≤ 5 000, 2 ≤ L ≤ 10 000.

0 < p_i < L, 2 ≤ q_i ≤ T, 0 ≤ s_i < e_i ≤ q_i (oraz 0 < s_i lub e_i < q_i).

Przykład

3 6 3 5
3 4 2 4
2 2 1 2
5 5 0 1

1