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 heapq import *

# G : [to/from, cap, cost, rev]
def minimumCostFlow(N: int, G: list, s: int, t: int, flow: int):
	ret = 0
	INF = 1 << 60
	potential = [0] * N
	pre_vtx = [None] * N
	pre_edge = [None] * N

	while flow > 0:
		dist = [INF] * N
		dist[s] = 0
		visited = [False] * N
		q = [(0, s)]
		while q:
			d, cur = heappop(q)
			if visited[cur]:
				continue
			visited[cur] = True
			for i in range(len(G[cur])):
				e = G[cur][i]
				nxt = e[0]
				if e[1] > 0 and dist[nxt] > dist[cur] + e[2] + potential[cur] - potential[nxt]:
					dist[nxt] = dist[cur] + e[2] + potential[cur] - potential[nxt]
					pre_vtx[nxt] = cur
					pre_edge[nxt] = i
					heappush(q, (dist[nxt], nxt))
		if dist[t] == INF:
			return -1
		for i in range(N):
			potential[i] += dist[i]
		df = flow
		now = t
		while now != s:
			df = min(df, G[pre_vtx[now]][pre_edge[now]][1])
			now = pre_vtx[now]
		flow -= df
		ret += df * potential[t]
		now = t
		while now != s:
			G[pre_vtx[now]][pre_edge[now]][1] -= df
			G[now][G[pre_vtx[now]][pre_edge[now]][3]][1] += df
			now = pre_vtx[now]
	return ret


import sys
input = sys.stdin.buffer.readline


def main():
	N, M, F = map(int, input().split())
	G = [[] for _ in range(N)]  # [to/from, cap, cost, rev]
	for _ in range(M):
		u, v, c, d = map(int, input().split())
		G[u].append([v, c, d, len(G[v])])
		G[v].append([u, 0, -d, len(G[u]) - 1])
	print(minimumCostFlow(N, G, 0, N - 1, F))


if __name__ == '__main__':
	main()