Problem description

Wielomianowy Wywiad Wojskowy to tajna służba specjalna, gromadząca informacje wywiadowcze w celu obrony złożoności obliczeniowej algorytmów. Od jakiegoś czasu WWW przygląda się poczynaniom organizacji K-SAT, która rzekomo prowadzi badania nad bronią zmieniającą dowolnie klasę złożoności problemów. Następnym ruchem wywiadu będzie wysłanie do kompleksu badawczego K-SATu szpiega – Agenta 00111.

Kompleks badawczy organizacji składa się z sektorów, ponumerowanych od 1 do N oraz dwukierunkowych przejść między nimi, ponumerowanych od 1 do M. 00111 pod osłoną nocy zakradnie się do jednego z sektorów. Następnie, korzystając z istniejących przejść (z niektórych być może wiele razy), odwiedzi pewną część pozostałych sektorów w celu zebrania informacji. Zadanie nie jest jednak takie proste. Każde przejście posiada dwa parametry – R_i oraz S_i, które oznaczają kolejno ryzyko wykrycia przez członka organizacji oraz ryzyko wzniesienia alarmu przez automatyczne czujniki. Rozważmy trasę szpiega korzystającą z przejść o numerach p₁, p₂, ..., p_k. Wskaźnikiem ryzyka takiej trasy nazywamy wartość wyrażenia $X \cdot \max\limits_{1 \le i \le k} (R_{p_i}) + Y \cdot \max\limits_{1 \le i \le k} (S_{p_i})$, gdzie X i Y to ustalone wcześniej stałe. Jeżeli wskaźnik ryzyka jest mniejszy lub równy K, to trasa jest biezpieczna.

Twoim zadaniem jest ustalenie największej możliwej liczby sektorów, które Agent jest w stanie odwiedzić rozpoczynając misję w dowolnym sektorze i korzystając z trasy, która jest bezpieczna. Pospiesz się! Wkrótce ten problem może okazać się NP-trudny.

Napisz program, który: wczyta opis kompleksu i stałe X, Y i K, wyznaczy maksymalną liczbę odwiedzonych sektorów i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się cztery liczby naturalne N, M, X, Y oraz K, pooddzielane pojedynczymi odstępami i oznaczające odpowiednio liczbę sektorów, liczbę przejść, stałe we wzorze na wskaźnik ryzyka oraz maksymalną bezpieczną wartość wskaźnika. Każdy z kolejnych M wierszy zawiera cztery liczby całkowite – A_i, B_i, R_i, S_i (A_i ≠ B_i), oznaczające przejście łączące sektory o numerach A_i i B_i oraz jego parametry. Między dwoma różnymi sektorami może istnieć więcej niż jedno przejście.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita – największa możliwa liczba sektorów, które Agent jest w stanie odwiedzić.

Ograniczenia

1 ≤ N, M ≤ 100 000, 1 ≤ X, Y, K, R_i, S_i ≤ 10⁹.

Przykład

3 3 1 1 10
1 2 3 8
1 3 7 4
2 3 5 5

2

4 6 5 2 24
1 2 1 6
1 3 4 1
2 3 3 3
2 1 2 5
2 4 1 1
4 3 5 6

3