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.