def dfs(v, t, f):
    if v == t: return f
    used[v] = True
    for to in G[v]:
        if to not in used and G[v][to] > 0:
            d = dfs(to, t, min(f, G[v][to]))
            if d > 0:
                G[v][to] -= d
                G[to][v] += d
                return d
    return 0

N, M, d = map(int, input().split())
G = {}
G[(1, 0)]      = {}
G[(N, 10**9)] = {}
T = [set() for _ in range(N+1)]
T[1].add(0)
T[N].add(10**9)
for _ in range(M):
    u, v, p, q, c = map(int, input().split())
    if v < N: q += d
    x = (u, p)
    y = (v, q)
    if x not in G: G[x]= {}
    if y not in G: G[y]= {}
    G[x][y] = c
    G[y][x] = 0
    T[u].add(p)
    T[v].add(q)

for i in range(1, N+1):
    t = sorted(T[i])
    for j in range(1, len(t)):
        x = (i, t[j-1])
        y = (i, t[j])
        G[x][y] = float('inf')
        G[y][x] = 0

flow = 0
while True:
    used = {}
    f = dfs((1, 0), (N, 10**9), float('inf'))
    if f == 0: break
    flow += f
print(flow)