8645번 - Strajk 다국어

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 p₁, p₂, ..., p_k, taki że węgiel z kopalni jest ładowany do pociągu p₁, następnie kolejno dla i = 1, ..., k - 1 węgiel jest przeładowywany z pociągu p_i do pociągu p_i+1, aż w końcu pociągiem p_k 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 k minut. Zamierzają tak wybrać pociąg, aby sumaryczne opóźnienie wszystkich pociągów było maksymalne.

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

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

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.

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.