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:
V,E,F=map(int,input().split())
EDGE=dict()
EDGE2=[[] for i in range(V)]

for i in range(E):
    x,to,c,d=map(int,input().split())
    EDGE[(x,to)]=[c,d]
    EDGE2[x].append(to)

BACK=[-1]*V
P=[0]*V

# 一回ベルマンフォードをしてポテンシャルを求める.

ANS=[float("inf")]*V
ANS[0]=0

for rep in range(V):    
    for x,to in EDGE:
        c,d=EDGE[(x,to)]
        if c>0 and ANS[to]>ANS[x]+d:
            ANS[to]=ANS[x]+d
            BACK[to]=x

P=[ANS[i] for i in range(V)]
LA=ANS[V-1]

NOW=V-1
while NOW!=0:
    fr=BACK[NOW]
    EDGE[(fr,NOW)][0]-=1

    if (NOW,fr) in EDGE:
        EDGE[(NOW,fr)][0]+=1
    else:
        EDGE[(NOW,fr)]=[1,-EDGE[fr,NOW][1]]
        EDGE2[NOW].append(fr)

    NOW=fr
    
for x,to in EDGE:
    EDGE[(x,to)][1]+=P[x]-P[to]

# あとはダイクストラを使える.

import heapq

for i in range(F-1):
    ANS=[float("inf")]*V
    Q=[(0,0)]
    ANS[0]=0

    while Q:
        time,ind=heapq.heappop(Q)
        if time>ANS[ind]:
            continue

        for to in EDGE2[ind]:
            c,d=EDGE[(ind,to)]
            if c>0 and ANS[to]>ANS[ind]+d:
                ANS[to]=ANS[ind]+d
                BACK[to]=ind
                heapq.heappush(Q,(ANS[to],to))

    LA+=ANS[V-1]+P[V-1]-P[0]

    if LA==float("inf"):
        break

    P=[P[i]-ANS[i] for i in range(V)]

    NOW=V-1
    while NOW!=0:
        fr=BACK[NOW]
        EDGE[(fr,NOW)][0]-=1

        if (NOW,fr) in EDGE:
            EDGE[(NOW,fr)][0]+=1
        else:
            EDGE[(NOW,fr)]=[1,-EDGE[fr,NOW][1]]
            EDGE2[NOW].append(fr)

        NOW=fr

    for x,to in EDGE:
        EDGE[(x,to)][1]+=ANS[to]-ANS[x]
    

if LA==float("inf"):
    print(-1)
else:
    print(LA)