#!/usr/bin/ python3.8 import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines from collections import defaultdict INF = 10**18 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, readline().split()) m = map(int, read().split()) U, V, P, Q, W = zip(*zip(m, m, m, m, m)) # U, V, P, Q, W = [], [], [], [], [] # for _ in range(M): # u,v,p,q,w = map( int, input().split()) # U.append(u) # V.append(v) # P.append(p) # Q.append(q) # W.append(w) X = [(u << 32) + p for u, p in zip(U, P)] Y = [(v << 32) + q + D for v, q in zip(V, Q)] nodes = sorted(set(X + Y)) ind = {x: i for i, x in enumerate(nodes)} L = len(nodes) source = L sink = L + 1 G = [[] for _ in range(L+2)] capacity = defaultdict( int) u, t = divmod(nodes[0], 1 << 32) if u == 1: G[source].append(0) capacity[(source, 0)] = INF G[0].append(source) u, t = divmod(nodes[-1], 1 << 32) if u == N: G[L-1].append(sink) capacity[(L-1, sink)] = INF G[sink].append(L-1) for i, (x, y) in enumerate(zip(nodes, nodes[1:])): if x >> 32 == y >> 32: G[i].append(i+1) capacity[(i, i+1)] = INF G[i+1].append(i) for x, y, w in zip(X, Y, W): G[ind[x]].append(ind[y]) capacity[(ind[x], ind[y])] += w G[ind[y]].append(ind[x]) print( Ford_Fulkerson(L+2,G,capacity,source,sink)) if __name__ == '__main__': main()