Problem Statement

An airline called "Air E869120" operates $M$ flights every day within the country of yuki.
The country of yuki consists of $N$ cities, numbered city $1$, $2$, $3$, ..., $N$. The $i$-th flight flies from city $u_i$ to city $v_i$, taking off from its origin at time $p_i$ and landing at its destination at time $q_i$. In addition, this flight can carry $w_i$ people.

Starting on 2018/11/01, a school in city $1$ is scheduled to hold a school trip to city $N$.
By coincidence, all flights on 2018/11/01 are completely empty, but all bookable flights after that date are fully booked. Also, the principal of this school does not trust any airline other than "Air E869120", so no flights other than those of this airline can be used.

Find the maximum number of students who can go on the school trip.
Here, students can board a flight that takes off at time $0$, and it suffices for them to be at the airport of city $N$ at the end of the day (time $10^9$). Also, since transfers take time, students must leave at least $d$ minutes between the landing time of the previous flight and the takeoff time of the next flight. The school has sufficiently many students, so you may assume there are infinitely many of them.

Input

$N$ $M$ $d$
$u_1$ $v_1$ $p_1$ $q_1$ $w_1$
$u_2$ $v_2$ $p_2$ $q_2$ $w_2$
$u_3$ $v_3$ $p_3$ $q_3$ $w_3$
......
$u_M$ $v_M$ $p_M$ $q_M$ $w_M$

Constraints

• $2 \le N \le 1000$
• $1 \le M \le 1000$
• $1 \le d \le 10^9$
• $1 \le u_i, v_i \le N, u_i ≠ v_i$
• $0 \le p_i < q_i \le 10^9$
• $1 \le w_i \le 10^9$

Output

Output on one line the maximum number of people who can travel on the school trip.
Print a newline at the end.

Sample

2 2 5
1 2 0 25 10
1 2 10 40 5

15

4 5 5
1 2 0 15 40
1 3 5 20 10
2 3 30 40 20
2 4 50 80 20
3 4 50 70 30

50

3 4 5
1 2 0 10 10
1 2 10 20 3
2 3 15 25 2
2 3 5 15 10

2

4 3 5
1 2 0 10 100
2 3 15 31 100
3 4 35 45 100

0

4 40 9
2 3 90 99 43
2 3 12 60 56
1 3 5 9 30
4 3 76 96 88
2 4 76 86 66
1 2 36 91 5
2 1 23 82 87
1 4 66 83 12
1 2 2 33 72
4 1 2 90 30
3 2 32 84 25
4 2 13 99 56
4 3 49 56 94
1 3 29 42 31
1 2 86 88 93
3 4 43 51 28
3 4 5 69 60
3 1 3 4 39
1 4 7 73 99
3 2 31 85 94
1 2 89 94 94
2 1 34 70 62
3 4 39 94 63
4 1 23 30 96
3 4 41 81 29
4 3 57 62 48
3 2 33 54 27
3 1 44 73 44
3 2 50 70 19
4 2 19 36 82
4 2 95 97 94
3 4 20 58 10
1 4 4 97 33
2 3 46 58 58
3 1 0 80 45
4 1 1 76 43
3 2 16 97 9
3 1 13 16 45
2 4 4 16 12
2 3 68 98 12

240