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_{1}, p_{2}, \ldots, p_{k}$, taki że węgiel z kopalni jest ładowany do pociągu $p_{1}$, następnie kolejno dla $i = 1, \ldots, 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.

Input Format

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite $n$ oraz $m$ ($2 \le n \le 400$, $1 \le m \le 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 \le k \le 10^{9}$) - 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 \le a_{i}, b_{i} \le n$, $0 \le w_{i}, p_{i} \le 10^{9}$, $0 \le w_{i} + p_{i} \le 10^{9}$). 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^{9} + 1$ minut). Czasy wyjazdów pociągów z miasta $m$ są nie mniejsze od największego czasu przyjazdu pociągu do $m$.

Output Format

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.

Examples

Input

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

Output

8