Strike

Byteland is proud to own the largest lignite (brown coal) mine in the world. Every day, coal from the mine is carried across the railway network to every city in Byteland so that residents have something to burn in their stoves.

Transport works like this: first, some trains set out from the city with the mine toward a few other cities; then from those cities more trains depart to still other cities, and so on. For every city in Byteland there is at least one sequence of trains $p_1, p_2, \dots, p_k$ such that coal from the mine is loaded onto train $p_1$, then for each $i = 1, \dots, k-1$ the coal is transferred from train $p_i$ to train $p_{i+1}$, until it finally reaches that city on train $p_k$. Several trains may arrive at any city (except the city with the mine), but there are no cycles: once you board a train in some city, you can never return to that city by rail.

The trains are coordinated: departure times are set so that a train leaving a city departs only after every scheduled coal train has arrived at that city. If a train is delayed, it may in turn delay other trains. The railway workers are planning a strike: they can hold exactly one train for $k$ minutes. They want to pick the train so that the total delay over all trains is as large as possible.

Compute that maximum total delay.

The first line contains two integers $n$ and $m$ ($2 \le n \le 400$, $1 \le m \le 80\,000$): the number of cities in Byteland and the number of direct rail connections. The second line contains one integer $k$ ($1 \le k \le 10^9$): the number of minutes for which the workers can hold one train. Cities are numbered from $1$ to $n$; the mine is in city $1$.

Each of the next $m$ lines contains four integers $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$). They mean that, on schedule, the $i$-th train leaves city $a_i$ exactly $w_i$ minutes after sunrise and arrives at city $b_i$ exactly $p_i$ minutes later, on the same day (a Byteland day lasts $10^9 + 1$ minutes). For every city, the departure times of the trains leaving it are not smaller than the largest arrival time of any train arriving at it.

Print a single integer: the maximum total delay of the trains that the workers' strike can cause.

For example, holding for $3$ minutes the train that runs from city $1$ to city $3$ delays that train together with the two trains departing from city $3$.