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:
import sys
input = sys.stdin.readline
from heapq import heappush, heappop
def min_cost_flow_dijkstra(E, s, t, f):
    INF = 1 << 100
    NN = N
    LN = NN.bit_length()
    G = [[] for _ in range(NN)]
    for a, b, cap, c in E:
        G[a].append([b, cap, c, len(G[b])])
        G[b].append([a, 0, -c, len(G[a])-1])
    prevv = [-1] * NN
    preve = [-1] * NN
    res = 0
    while f > 0:
        h = [0] * NN
        dist = [INF] * NN
        dist[s] = 0
        Q = []
        heappush(Q, s)
        while len(Q):
            x = heappop(Q)
            d, v = (x>>LN), x % (1<<LN)
            if dist[v] < d: continue
            for i, (w, _cap, c, r) in enumerate(G[v]):
                if _cap > 0 and dist[w] > dist[v] + c + h[v] - h[w]:
                    dist[w] = dist[v] + c + h[v] - h[w]
                    prevv[w] = v
                    preve[w] = i
                    heappush(Q, (dist[w] << LN) + w)
        if dist[t] == INF:
            return -1
        for v in range(N):
            h[v] += dist[v]
        
        d = f
        v = t
        while v != s:
            d = min(d, G[prevv[v]][preve[v]][1])
            v = prevv[v]
        f -= d
        res += d * dist[t]
        v = t
        while v != s:
            G[prevv[v]][preve[v]][1] -= d
            G[v][G[prevv[v]][preve[v]][3]][1] += d
            v = prevv[v]
    return res

N, M, F = map(int, input().split())
E = []
for i in range(M):
    u, v, c, d = map(int, input().split())
    E.append((u, v, c, d))

print(min_cost_flow_dijkstra(E, 0, N-1, F))