import sys input = sys.stdin.readline from collections import defaultdict INF = 10**15 def dfs_for_Ford_Fulkerson(N,E,capacity,s,g,flowing): stack = [(s,INF)] root = [0]*N root[s] = -1 V = [False]*N V[s] = True while stack: u, flow = stack.pop() for v in E[u]: if not V[v] and capacity[(u,v)] > 0: root[v] = u V[v] = True if v == g: if capacity[(u,v)] < flow: flow = capacity[(u,v)] break stack.append((v, min(flow, capacity[(u,v)]))) else: continue break else: return False now = g while now != s: before = root[now] capacity[(before, now)] -= flow capacity[(now, before)] += flow now = before flowing[0] += flow return True def Ford_Fulkerson(N,E,capacity, s, g): flowing = [0] while dfs_for_Ford_Fulkerson(N,E,capacity,s,g, flowing): pass return flowing[0] def main(): N, M, d = map( int, input().split()) UVPQW = [ tuple( map( int, input().split())) for _ in range(M)] E = [set() for _ in range(N)] L = 10**9 E[0].add(0) E[N-1].add(L) for u, v, p, q, _ in UVPQW: u, v = u-1, v-1 if q+d <= L: E[u].add(p) E[v].add(q+d) F = [sorted(list(E[i])) for i in range(N)] index = 0 VtoI = defaultdict( int) for i in range(N): for v in F[i]: VtoI[(i,v)] = index index += 1 I = index G = [[] for _ in range(I)] capacity = defaultdict( int) for u,v,p,q,w in UVPQW: u, v = u-1, v-1 q += d if q > L: continue a = VtoI[(u,p)] b = VtoI[(v,q)] G[a].append(b) capacity[(a,b)] = +w G[b].append(a) for i in range(N): lg = len(F[i]) for j in range(lg-1): a = VtoI[(i,F[i][j])] b = VtoI[(i, F[i][j+1])] G[a].append(b) capacity[(a,b)] = INF G[b].append(a) s = VtoI[(0,0)] g = VtoI[(N-1,L)] print( Ford_Fulkerson(I,G,capacity,s,g)) if __name__ == '__main__': main()