Strajk [A]

Limit pamięci: 128 MB

Bajtocja szczyci się posiadaniem największej na świecie kopalni węgla brunatnego. Codziennie węgiel z kopalni jest transportowany siecią kolejową do wszystkich bajtockich miast, aby mieszkańcy mieli czym palić w piecach.

Transport odbywa się w ten sposób, że najpierw pewna liczba pociągów wyrusza z miasta, w którym znajduje się kopalnia, do kilku innych miast, następnie z tamtych miast odjeżdżają kolejne pociągi do jeszcze innych miast i tak dalej. Dla każdego miasta Bajtocji istnieje co najmniej jeden ciąg pociągów , taki że węgiel z kopalni jest ładowany do pociągu , następnie kolejno dla węgiel jest przeładowywany z pociągu do pociągu , aż w końcu pociągiem dociera do tego miasta. Do każdego miasta (oprócz miasta z kopalnią) może przyjeżdżać kilka pociągów, jednak nie występują pętle - jeżeli w danym mieście wsiądziemy do pociągu, to na pewno drogą kolejową już do niego nie wrócimy.

Pociągi są skomunikowane - czasy odjazdu są tak dobrane, że pociągi wyruszają z danego miasta dopiero po tym, jak już przyjadą do niego wszystkie zaplanowane pociągi z węglem z kopalni. Jeżeli pociąg będzie się opóźniał, to może to także spowodować opóźnienia innych pociągów. Kolejarze planują strajk: mogą zatrzymać dokładnie jeden pociąg na minut. Zamierzają tak wybrać pociąg, aby sumaryczne opóźnienie wszystkich pociągów było maksymalne.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite oraz (, ), oznaczające liczbę miast w Bajtocji i liczbę bezpośrednich połączeń kolejowych. Następny wiersz zawiera jedną liczbę całkowitą () - maksymalne opóźnienie pociągu zatrzymanego przez kolejarzy. Miasta numerujemy liczbami od 1 do ; kopalnia znajduje się w mieście o numerze 1.

W każdym z następnych wierszy znajdują się po cztery liczby całkowite , , , (, , ). Oznaczają one, że zgodnie z rozkładem -ty pociąg wyjeżdża z miasta punktualnie minut po wschodzie słońca i przyjeżdża do miasta punktualnie minut później, tego samego dnia (bajtocki dzień ma minut). Czasy wyjazdów pociągów z miasta są nie mniejsze od największego czasu przyjazdu pociągu do .

Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą - maksymalne sumaryczne opóźnienie pociągów, jakie może spowodować strajk kolejarzy.

Przykład

Dla danych wejściowych:

5 5
3
1 2 3 1
1 3 0 3
3 2 4 1
3 4 3 5
2 5 8 2

poprawną odpowiedzią jest:

8

Wyjaśnienie do przykładu: Zatrzymanie na 3 minuty pociągu jadącego z miasta 1 do miasta 3 spowoduje opóźnienie tego pociągu oraz dwóch pociągów wyruszających z miasta 3.

Autor zadania: Bartosz Tarnawski.