Byteotia prides itself on having the world's largest lignite mine. Every day, coal from the mine is transported via a railway network to all Byteotian cities so that residents have fuel for their stoves.

The transport is organized such that a certain number of trains first depart from the city where the mine is located to several other cities, then subsequent trains depart from those cities to even more cities, and so on. For every city in Byteotia, there exists at least one sequence of trains $p_{1}, p_{2}, \ldots, p_{k}$ such that coal from the mine is loaded onto train $p_{1}$, then sequentially for $i = 1, \ldots, k - 1$ the coal is transferred from train $p_{i}$ to train $p_{i+1}$, until it finally reaches the city via train $p_{k}$. Several trains may arrive at each city (except for the city with the mine), but there are no cycles—if you board a train in a given city, you will certainly not return to it by rail.

The trains are synchronized—departure times are set such that trains depart from a given city only after all scheduled coal trains from the mine have arrived there. If a train is delayed, it may also cause delays to other trains. The railway workers are planning a strike: they can stop exactly one train for $k$ minutes. They intend to choose the train such that the total delay of all trains is maximized.

Input

The first line of input contains two integers $n$ and $m$ ($2 \le n \le 400$, $1 \le m \le 80\,000$), representing the number of cities in Byteotia and the number of direct railway connections. The next line contains a single integer $k$ ($1 \le k \le 10^{9}$) — the maximum delay of a train stopped by the railway workers. Cities are numbered from 1 to $n$; the mine is located 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}$). These indicate that, according to the schedule, the $i$-th train departs from 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 Byteotian day has $10^{9} + 1$ minutes). The departure times of trains from city $m$ are no earlier than the latest arrival time of a train to $m$.

Output

The first and only line of standard output should contain a single integer — the maximum total delay of trains that the railway workers' strike can cause.

Examples

Input 1

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

Output 1

8