Problem: Examples

Input

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


Output

6


Input




Output

Solution (in PYTHON3):

Solution:
from typing import List, Iterator, Optional, Tuple


def trace_back(sink: int,
               predecessors: List[Optional[Tuple[int, int]]]) -> Iterator[List[int]]:
    p = predecessors[sink]
    while p is not None:
        v, i = p
        yield edges[v][i]
        p = predecessors[v]


def min_cost_flow(source: int, sink: int, required_flow: int) -> int:
    res = 0
    while required_flow:
        dist = [float('inf')] * n
        dist[source] = 0
        predecessors: List[Optional[Tuple[int, int]]] = [None] * n

        while True:
            updated = False
            for v in range(n):
                if dist[v] == float('inf'):
                    continue
                for i, (remain, target, cost, _) in enumerate(edges[v]):
                    new_dist = dist[v] + cost
                    if remain and dist[target] > new_dist:
                        dist[target] = new_dist
                        predecessors[target] = (v, i)
                        updated = True
            if not updated:
                break

        if dist[sink] == float('inf'):
            return -1

        aug = min(required_flow, min(e[0] for e in trace_back(sink, predecessors)))
        required_flow -= aug
        res += int(aug * dist[sink])
        for e in trace_back(sink, predecessors):
            remain, target, cost, idx = e
            e[0] -= aug
            edges[target][idx][0] += aug
    return res


if __name__ == "__main__":
    n, m, f = map(int, input().split())
    edges = [[] for _ in range(n)]  # type: ignore

    for _ in range(m):
        s, t, c, d = map(int, input().split())
        es, et = edges[s], edges[t]
        ls, lt = len(es), len(et)
        es.append([c, t, d, lt])
        et.append([0, s, -d, ls])

    print(min_cost_flow(0, n - 1, f))