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

Source: aizu | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
from collections import defaultdict
from heapq import *

class MinCostFlow:

	def __init__(self):
		self.inf = 10 ** 9
		self.to = defaultdict(dict)

	def add_edge(self, u, v, cap, cost):
		self.to[u][v] = [cap, cost]
		self.to[v][u] = [0, -cost]

	def cal(self, s, t, f):
		min_cost = 0
		pot = defaultdict(int)
		while f:
			dist = {}
			pre_u = {}
			hp = []
			heappush(hp, (0, s))
			dist[s] = 0
			while hp:
				(d, u) = heappop(hp)
				if d > dist[u]:
					continue
				for (v, [cap, cost]) in self.to[u].items():
					if cap == 0:
						continue
					nd = dist[u] + cost + pot[u] - pot[v]
					dist.setdefault(v, self.inf)
					if nd >= dist[v]:
						continue
					dist[v] = nd
					pre_u[v] = u
					heappush(hp, (nd, v))
			if t not in dist:
				return -1
			for (u, d) in dist.items():
				pot[u] += d
			u = t
			min_cap = f
			while u != s:
				(u, v) = (pre_u[u], u)
				min_cap = min(min_cap, self.to[u][v][0])
			f -= min_cap
			min_cost += min_cap * pot[t]
			u = t
			while u != s:
				(u, v) = (pre_u[u], u)
				self.to[u][v][0] -= min_cap
				self.to[v][u][0] += min_cap
		return min_cost

def main():
	(n, m, f) = map(int, input().split())
	mc = MinCostFlow()
	for _ in range(m):
		(u, v, c, d) = map(int, input().split())
		mc.add_edge(u, v, c, d)
	print(mc.cal(0, n - 1, f))
main()


import heapq

class MinCostFlow:

	class Edge:

		def __init__(self, to, cap, rev, cost):
			self.to = to
			self.cap = cap
			self.rev = rev
			self.cost = cost

	def __init__(self, n, inf=1000000007):
		self.n = n
		self.inf = inf
		self.e = [[] for _ in range(n)]

	def add_edge(self, fr, to, cap, cost):
		self.e[fr].append(self.Edge(to, cap, len(self.e[to]), cost))
		self.e[to].append(self.Edge(fr, 0, len(self.e[fr]) - 1, -cost))

	def compute(self, source, sink, f):
		res = 0
		h = [0] * self.n
		prevv = [0] * self.n
		preve = [0] * self.n
		while f > 0:
			pq = []
			dist = [self.inf] * self.n
			dist[source] = 0
			heapq.heappush(pq, (0, source))
			while pq:
				(cost, v) = heapq.heappop(pq)
				cost = -cost
				if dist[v] < cost:
					continue
				for (i, edge) in enumerate(self.e[v]):
					if edge.cap > 0 and dist[v] - h[edge.to] < dist[edge.to] - edge.cost - h[v]:
						dist[edge.to] = dist[v] + edge.cost + h[v] - h[edge.to]
						prevv[edge.to] = v
						preve[edge.to] = i
						heapq.heappush(pq, (-dist[edge.to], edge.to))
			if dist[sink] == self.inf:
				return -1
			for v in range(self.n):
				h[v] += dist[v]
			(d, v) = (f, sink)
			while v != source:
				d = min(d, self.e[prevv[v]][preve[v]].cap)
				v = prevv[v]
			f -= d
			res += d * h[sink]
			v = sink
			while v != source:
				self.e[prevv[v]][preve[v]].cap -= d
				self.e[v][self.e[prevv[v]][preve[v]].rev].cap += d
				v = prevv[v]
		return res

def main():
	(v, e, f) = map(int, input().split())
	MCF = MinCostFlow(v)
	for _ in range(e):
		(a, b, c, d) = map(int, input().split())
		MCF.add_edge(a, b, c, d)
	print(MCF.compute(0, v - 1, f))
main()


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))


class MinCostFlow:

	def __init__(self, n):
		self.n = n
		self.G = [[] for i in range(n)]

	def addEdge(self, f, t, cap, cost):
		self.G[f].append([t, cap, cost, len(self.G[t])])
		self.G[t].append([f, 0, -cost, len(self.G[f]) - 1])

	def minCostFlow(self, s, t, f):
		n = self.n
		G = self.G
		prevv = [0] * n
		preve = [0] * n
		INF = 10 ** 9 + 7
		res = 0
		while f:
			dist = [INF] * n
			dist[s] = 0
			update = 1
			while update:
				update = 0
				for v in range(n):
					if dist[v] == INF:
						continue
					gv = G[v]
					for i in range(len(gv)):
						(to, cap, cost, rev) = gv[i]
						if cap > 0 and dist[v] + cost < dist[to]:
							dist[to] = dist[v] + cost
							prevv[to] = v
							preve[to] = i
							update = 1
			if dist[t] == INF:
				return -1
			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:
				e = G[prevv[v]][preve[v]]
				e[1] -= d
				G[v][e[3]][1] += d
				v = prevv[v]
		return res
(n, m, f) = map(int, input().split())
graph = MinCostFlow(n)
for i in range(m):
	(u, v, c, d) = map(int, input().split())
	graph.addEdge(u, v, c, d)
print(graph.minCostFlow(0, n - 1, f))


import sys
readline = sys.stdin.buffer.readline

def even(n):
	return 1 if n % 2 == 0 else 0
(n, m, f) = map(int, readline().split())

class MinCostFlow:

	def __init__(self, n):
		self.n = n
		self.G = [[] for i in range(n)]

	def addEdge(self, f, t, cap, cost):
		self.G[f].append([t, cap, cost, len(self.G[t])])
		self.G[t].append([f, 0, -cost, len(self.G[f]) - 1])

	def minCostFlow(self, s, t, f):
		n = self.n
		G = self.G
		prevv = [0] * n
		preve = [0] * n
		INF = 10 ** 18
		res = 0
		while f:
			dist = [INF] * n
			dist[s] = 0
			update = 1
			while update:
				update = 0
				for v in range(n):
					if dist[v] == INF:
						continue
					gv = G[v]
					for i in range(len(gv)):
						(to, cap, cost, rev) = gv[i]
						if cap > 0 and dist[v] + cost < dist[to]:
							dist[to] = dist[v] + cost
							prevv[to] = v
							preve[to] = i
							update = 1
			if dist[t] == INF:
				return -1
			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:
				e = G[prevv[v]][preve[v]]
				e[1] -= d
				G[v][e[3]][1] += d
				v = prevv[v]
		return res
MCF = MinCostFlow(n)
for i in range(m):
	(u, v, cap, cost) = map(int, readline().split())
	MCF.addEdge(u, v, cap, cost)
print(MCF.minCostFlow(0, n - 1, f))


from heapq import heappush, heappop

class MinimumCostFlow:
	inf = 1000000000

	def __init__(self, n):
		self.n = n
		self.edges = [[] for i in range(n)]

	def add_edge(self, f, t, cap, cost):
		self.edges[f].append([t, cap, cost, len(self.edges[t]), False])
		self.edges[t].append([f, 0, -cost, len(self.edges[f]) - 1, True])

	def flow(self, s, t, flow):
		n = self.n
		g = self.edges
		inf = MinimumCostFlow.inf
		prevv = [0 for i in range(n)]
		preve = [0 for i in range(n)]
		h = [0 for i in range(n)]
		dist = [inf for i in range(n)]
		res = 0
		while flow != 0:
			dist = [inf for i in range(n)]
			dist[s] = 0
			que = [(0, s)]
			while que:
				(c, v) = heappop(que)
				if dist[v] < c:
					continue
				r0 = dist[v] + h[v]
				for (i, e) in enumerate(g[v]):
					(w, cap, cost, _, _) = e
					if cap > 0 and r0 + cost - h[w] < dist[w]:
						r = r0 + cost - h[w]
						dist[w] = r
						prevv[w] = v
						preve[w] = i
						heappush(que, (r, w))
			if dist[t] == inf:
				return -1
			for i in range(n):
				h[i] += dist[i]
			d = flow
			v = t
			while v != s:
				d = min(d, g[prevv[v]][preve[v]][1])
				v = prevv[v]
			flow -= d
			res += d * h[t]
			v = t
			while v != s:
				e = g[prevv[v]][preve[v]]
				e[1] -= d
				g[v][e[3]][1] += d
				v = prevv[v]
		return res
import sys
readline = sys.stdin.readline
write = sys.stdout.write
(N, M, F) = map(int, readline().split())
mcf = MinimumCostFlow(N)
for i in range(M):
	(u, v, c, d) = map(int, readline().split())
	mcf.add_edge(u, v, c, d)
write('%d\n' % mcf.flow(0, N - 1, F))


(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)


INF = float('inf')

def trace_back(sink, predecessors):
	p = predecessors[sink]
	while p is not None:
		(v, i) = p
		yield edges[v][i]
		p = predecessors[v]

def min_cost_flow(source, sink, required_flow):
	res = 0
	while required_flow:
		dist = [INF] * n
		dist[source] = 0
		predecessors = [None] * n
		while True:
			updated = False
			for v in range(n):
				if dist[v] == 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] == INF:
			return -1
		aug = min(required_flow, min((e[0] for e in trace_back(sink, predecessors))))
		required_flow -= aug
		res += 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
(n, m, f) = map(int, input().split())
edges = [[] for _ in range(n)]
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))


from heapq import heappush, heappop

class MinCostFlow:
	INF = 10 ** 18

	def __init__(self, N):
		self.N = N
		self.G = [[] for i in range(N)]

	def add_edge(self, fr, to, cap, cost):
		G = self.G
		G[fr].append([to, cap, cost, len(G[to])])
		G[to].append([fr, 0, -cost, len(G[fr]) - 1])

	def flow(self, s, t, f):
		N = self.N
		G = self.G
		INF = MinCostFlow.INF
		res = 0
		H = [0] * N
		prv_v = [0] * N
		prv_e = [0] * N
		while f:
			dist = [INF] * N
			dist[s] = 0
			que = [(0, s)]
			while que:
				(c, v) = heappop(que)
				if dist[v] < c:
					continue
				for (i, (w, cap, cost, rev)) in enumerate(G[v]):
					if cap > 0 and dist[w] > dist[v] + cost + H[v] - H[w]:
						dist[w] = r = dist[v] + cost + H[v] - H[w]
						prv_v[w] = v
						prv_e[w] = i
						heappush(que, (r, w))
			if dist[t] == INF:
				return -1
			for i in range(N):
				H[i] += dist[i]
			d = f
			v = t
			while v != s:
				d = min(d, G[prv_v[v]][prv_e[v]][1])
				v = prv_v[v]
			f -= d
			res += d * H[t]
			v = t
			while v != s:
				e = G[prv_v[v]][prv_e[v]]
				e[1] -= d
				G[v][e[3]][1] += d
				v = prv_v[v]
		return res
import sys
readline = sys.stdin.readline
write = sys.stdout.write
(N, M, F) = map(int, readline().split())
mcf = MinCostFlow(N)
for i in range(M):
	(u, v, c, d) = map(int, readline().split())
	mcf.add_edge(u, v, c, d)
write('%d\n' % mcf.flow(0, N - 1, F))


from collections import defaultdict
(v_num, e_num, flow) = (int(n) for n in input().split(' '))
edges = defaultdict(list)
for _ in range(e_num):
	(s1, t1, cap, cost) = (int(n) for n in input().split(' '))
	edges[s1].append([t1, cap, cost, len(edges[t1])])
	edges[t1].append([s1, 0, -cost, len(edges[s1]) - 1])
answer = 0
before_vertice = [float('inf') for n in range(v_num)]
before_edge = [float('inf') for n in range(v_num)]
sink = v_num - 1
while True:
	distance = [float('inf') for n in range(v_num)]
	distance[0] = 0
	updated = 1
	while updated:
		updated = 0
		for v in range(v_num):
			if distance[v] == float('inf'):
				continue
			for (i, (target, cap, cost, trace_i)) in enumerate(edges[v]):
				if cap > 0 and distance[target] > distance[v] + cost:
					distance[target] = distance[v] + cost
					before_vertice[target] = v
					before_edge[target] = i
					updated = 1
	if distance[sink] == float('inf'):
		print(-1)
		break
	decreased = flow
	trace_i = sink
	while trace_i != 0:
		decreased = min(decreased, edges[before_vertice[trace_i]][before_edge[trace_i]][1])
		trace_i = before_vertice[trace_i]
	flow -= decreased
	trace_i = sink
	while trace_i != 0:
		this_edge = edges[before_vertice[trace_i]][before_edge[trace_i]]
		this_edge[1] -= decreased
		answer += this_edge[2] * decreased
		edges[trace_i][this_edge[3]][1] += decreased
		trace_i = before_vertice[trace_i]
	if flow <= 0:
		print(answer)
		break


import heapq as hp

class MinimumCostFlow:

	def __init__(self, N, INF=10 ** 18):
		self.graph = [{} for _ in range(N)]
		self.N = N
		self.INF = INF

	def add_edge(self, u, v, cap, cost, undirected=False):
		if cap == 0:
			return
		if undirected:
			self.graph[u][v] = [cap, cost]
			self.graph[v][u] = [cap, -cost]
		elif v in self.graph[u]:
			self.graph[u][v] = [cap, cost]
		else:
			self.graph[u][v] = [cap, cost]
			self.graph[v][u] = [0, -cost]

	def dijkstra(self, start):
		self.dist = [self.INF] * self.N
		self.dist[start] = 0
		self.que = [(0, start)]
		while self.que:
			(d, v) = hp.heappop(self.que)
			if self.dist[v] < d:
				continue
			for (nv, (ncap, ncost)) in self.graph[v].items():
				if ncap > 0 and self.dist[nv] > self.dist[v] + ncost + self.H[v] - self.H[nv]:
					self.dist[nv] = self.dist[v] + ncost + self.H[v] - self.H[nv]
					self.prevv[nv] = v
					hp.heappush(self.que, (self.dist[nv], nv))

	def min_cost_flow(self, start, finish, flow):
		self.res = 0
		self.prevv = [-1] * self.N
		self.H = [0] * self.N
		while flow > 0:
			self.dijkstra(start)
			if self.dist[finish] == self.INF:
				return -1
			for i in range(self.N):
				self.H[i] += self.dist[i]
			d = flow
			v = finish
			while v != start:
				d = min(d, self.graph[self.prevv[v]][v][0])
				v = self.prevv[v]
			flow -= d
			self.res += d * self.H[finish]
			v = finish
			while v != start:
				self.graph[self.prevv[v]][v][0] -= d
				self.graph[v][self.prevv[v]][0] += d
				v = self.prevv[v]
		return self.res
import sys
input = sys.stdin.readline
(V, E, F) = map(int, input().split())
fl = MinimumCostFlow(V)
for _ in range(E):
	(u, v, c, d) = map(int, input().split())
	fl.add_edge(u, v, c, d)
print(fl.min_cost_flow(0, V - 1, F))


import heapq

class PrimalDual:

	def __init__(self, n: int):
		self.INF = 10 ** 9 + 7
		self.n = n
		self.graph = [[] for _ in range(n)]

	def add_edge(self, _from: int, to: int, capacity: int, cost: int):
		forward = [to, capacity, cost, None]
		forward[3] = backward = [_from, 0, -cost, forward]
		self.graph[_from].append(forward)
		self.graph[to].append(backward)

	def min_cost_flow(self, s: int, t: int, f: int) -> int:
		res = 0
		potential = [0] * self.n
		prv_v = [0] * self.n
		prv_e = [None] * self.n
		while f > 0:
			dist = [self.INF] * self.n
			dist[s] = 0
			q = [(0, s)]
			while q:
				(cost, _from) = heapq.heappop(q)
				if dist[_from] < cost:
					continue
				for edge in self.graph[_from]:
					(to, capacity, cost, _) = edge
					p_diff = potential[_from] - potential[to]
					if capacity > 0 and dist[_from] + cost + p_diff < dist[to]:
						dist[to] = dist[_from] + cost + p_diff
						prv_v[to] = _from
						prv_e[to] = edge
						heapq.heappush(q, (dist[to], to))
			if dist[t] == self.INF:
				return -1
			for i in range(self.n):
				if dist[i] != self.INF:
					potential[i] += dist[i]
			d = f
			v = t
			while v != s:
				d = min(d, prv_e[v][1])
				v = prv_v[v]
			f -= d
			res += potential[t] * d
			v = t
			while v != s:
				edge = prv_e[v]
				edge[1] -= d
				edge[3][1] += d
				v = prv_v[v]
		return res
(n, m, f) = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(m)]
pd = PrimalDual(n)
for edge in edges:
	pd.add_edge(*edge)
ans = pd.min_cost_flow(0, n - 1, f)
print(ans)


import heapq

class MinCostFlow:

	class Edge:

		def __init__(self, to, cap, rev, cost):
			(self.to, self.cap, self.rev, self.cost) = (to, cap, rev, cost)

	def __init__(self, V):
		self.V = V
		self.E = [[] for _ in range(V)]

	def add_edge(self, fr, to, cap, cost):
		self.E[fr].append(self.Edge(to, cap, len(self.E[to]), cost))
		self.E[to].append(self.Edge(fr, 0, len(self.E[fr]) - 1, -cost))

	def run(self, source, sink, f, INF=10 ** 5):
		res = 0
		(h, prevv, preve) = ([0] * self.V, [0] * self.V, [0] * self.V)
		while f > 0:
			pque = []
			dist = [INF] * self.V
			dist[source] = 0
			heapq.heappush(pque, (0, source))
			while pque:
				(cost, v) = heapq.heappop(pque)
				cost = -cost
				if dist[v] < cost:
					continue
				for (i, e) in enumerate(self.E[v]):
					if e.cap > 0 and dist[v] - h[e.to] < dist[e.to] - e.cost - h[v]:
						dist[e.to] = dist[v] + e.cost + h[v] - h[e.to]
						(prevv[e.to], preve[e.to]) = (v, i)
						heapq.heappush(pque, (-dist[e.to], e.to))
			if dist[sink] == INF:
				return -1
			for v in range(self.V):
				h[v] += dist[v]
			(d, v) = (f, sink)
			while v != source:
				d = min(d, self.E[prevv[v]][preve[v]].cap)
				v = prevv[v]
			f -= d
			res += d * h[sink]
			v = sink
			while v != source:
				self.E[prevv[v]][preve[v]].cap -= d
				self.E[v][self.E[prevv[v]][preve[v]].rev].cap += d
				v = prevv[v]
		return res
(V, E, F) = map(int, input().split())
mcf = MinCostFlow(V)
for _ in range(E):
	(u, v, c, d) = map(int, input().split())
	mcf.add_edge(u, v, c, d)
print(mcf.run(0, V - 1, F))


from heapq import *

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)]
	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))
main()


import sys, collections
sys.setrecursionlimit(100000)
INF = float('inf')
(V, E, F) = map(int, sys.stdin.readline().split())
uvcd = tuple((tuple(map(int, sys.stdin.readline().rstrip().split())) for _ in range(E)))
capacityG = {i: {} for i in range(V)}
costG = {i: {} for i in range(V)}
for (u, v, c, d) in uvcd:
	capacityG[u][v] = c
	costG[u][v] = d
	if not u in capacityG[v]:
		capacityG[v][u] = 0
		costG[v][u] = -d

def shortest_path(V, costG, capacityG, start=0):
	distances = [INF] * V
	distances[start] = 0
	parents = list(range(V))
	for _ in range(V):
		modified = False
		for src in range(V):
			if distances[src] == INF:
				continue
			for (dst, cost) in costG[src].items():
				if capacityG[src][dst] > 0 and distances[dst] > distances[src] + cost:
					distances[dst] = distances[src] + cost
					parents[dst] = src
					modified = True
		if modified == False:
			return (distances, parents)
	return (None, None)
rest = F
total_cost = 0
while rest != 0:
	(distances, p) = shortest_path(V, costG, capacityG, 0)
	if not distances or distances[V - 1] == INF:
		print(-1)
		exit()
	cur = V - 1
	flow = rest
	while cur != 0:
		flow = min(flow, capacityG[p[cur]][cur])
		cur = p[cur]
	rest -= flow
	total_cost += distances[V - 1] * flow
	cur = V - 1
	while cur != 0:
		capacityG[p[cur]][cur] -= flow
		capacityG[cur][p[cur]] += flow
		cur = p[cur]
print(total_cost)


WEIGHT_MAX = 10 ** 10

class Edge:
	__slots__ = ('src', 'dest', 'capacity', 'flow', 'cost')

	def __init__(self, v, w, capacity, cost=0):
		self.src = v
		self.dest = w
		self.capacity = capacity
		self.cost = cost
		self.flow = 0

	def other(self, v):
		if v == self.src:
			return self.dest
		else:
			return self.src

	def residual_capacity(self, v):
		if v == self.src:
			return self.capacity - self.flow
		else:
			return self.flow

	def cost_from(self, v):
		if v == self.src:
			return self.cost
		else:
			return -self.cost

	def add_flow(self, v, f):
		if v == self.src:
			self.flow += f
		else:
			self.flow -= f

	def __str__(self):
		return '{} {} {} {} {}'.format(self.src, self.dest, self.capacity, self.cost, self.flow)

class Network:

	def __init__(self, v):
		self.v = v
		self._edges = [[] for _ in range(v)]

	def add(self, edge):
		self._edges[edge.src].append(edge)
		self._edges[edge.dest].append(edge)

	def adj(self, v):
		return self._edges[v]

	def flow(self, v):
		return sum((e.flow for e in self.adj(v) if e.src == v))

	def cost(self):
		cost = 0
		for v in range(self.v):
			for e in self.adj(v):
				if e.src == v:
					cost += e.flow * e.cost
		return cost

	def __str__(self):
		s = ''
		for v in range(self.v):
			for e in self.adj(v):
				s += '{} {}\n'.format(v, e)
		return s

def min_cost(network, s, t, f):

	def augment_path():

		def relax(edge, v):
			w = edge.other(v)
			c = edge.cost_from(v)
			if e.residual_capacity(v) > 0 and dists[w] > dists[v] + c:
				dists[w] = dists[v] + c
				edge_to[w] = e
				_nodes.append(w)
		dists = [WEIGHT_MAX] * network.v
		dists[s] = 0
		edge_to = [None] * network.v
		nodes = []
		nodes.append(s)
		for _ in range(network.v):
			_nodes = []
			for v in nodes:
				for e in network.adj(v):
					relax(e, v)
			nodes = _nodes
		if edge_to[t] is None:
			return (0, [])
		else:
			v = t
			e = edge_to[v]
			cap = f
			while e is not None:
				v = e.other(v)
				_cap = e.residual_capacity(v)
				if cap > _cap:
					cap = _cap
				e = edge_to[v]
			return (cap, edge_to)
	while f > 0:
		(cap, path) = augment_path()
		if cap == 0:
			break
		f -= cap
		v = t
		e = path[t]
		while e is not None:
			v = e.other(v)
			e.add_flow(v, cap)
			e = path[v]
	if f > 0:
		return -1
	else:
		return network.cost()

def run():
	(v, e, f) = [int(i) for i in input().split()]
	net = Network(v)
	(s, t) = (0, v - 1)
	for _ in range(e):
		(v, w, c, d) = [int(i) for i in input().split()]
		net.add(Edge(v, w, c, d))
	print(min_cost(net, s, t, f))
run()


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))

def ZIP(n):
	return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class MinCostFlow:

	def __init__(self, n):
		self.n = n
		self.g = [[] for i in range(n)]

	def add_edge(self, fr, to, cap, cost):
		G = self.g
		G[fr].append([to, cap, cost, len(G[to])])
		G[to].append([fr, 0, -cost, len(G[fr]) - 1])

	def flow(self, s, t, f):
		N = self.n
		G = self.g
		INF = 10 ** 18
		prevv = [0] * N
		preve = [0] * N
		res = 0
		while f > 0:
			dist = [INF] * N
			dist[s] = 0
			update = True
			while update:
				update = False
				for v in range(N):
					if dist[v] == INF:
						continue
					for i in range(len(G[v])):
						(to, cap, cost, rev) = G[v][i]
						if cap > 0 and dist[to] > dist[v] + cost:
							dist[to] = dist[v] + cost
							prevv[to] = v
							preve[to] = i
							update = True
			if dist[t] == INF:
				return -1
			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:
				e = G[prevv[v]][preve[v]]
				e[1] -= d
				G[v][e[3]][1] += d
				v = prevv[v]
		return res
(V, E, F) = MAP()
mcf = MinCostFlow(V)
for _ in range(E):
	(u, v, c, d) = MAP()
	mcf.add_edge(u, v, c, d)
print(mcf.flow(0, V - 1, F))


import os
import sys
from collections import defaultdict
import heapq
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(2147483647)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7

class MinCostFlow:

	def __init__(self, graph=None, residual=None):
		assert graph and (not residual) or (not graph and residual)
		if graph:
			self.graph = self.residual_graph(graph)
		else:
			self.graph = residual

	@staticmethod
	def residual_graph(graph):
		ret = [[] for _ in range(len(graph))]
		for v in range(len(graph)):
			for (u, cap, cost) in graph[v]:
				rev = [v, 0, -cost]
				edge = [u, cap, cost, rev]
				rev.append(edge)
				ret[v].append(edge)
				ret[u].append(rev)
		return ret

	def solve(self, from_v, to_v, flow):
		res = 0
		h = [0] * len(self.graph)
		prevv = [-1] * len(self.graph)
		preve = [-1] * len(self.graph)
		remains = flow
		while remains > 0:
			dist = [float('inf')] * len(self.graph)
			dist[from_v] = 0
			heap = [(0, from_v)]
			while heap:
				(d, v) = heapq.heappop(heap)
				if d > dist[v]:
					continue
				for edge in self.graph[v]:
					(u, cap, cost, rev) = edge
					if cap > 0 and dist[v] + cost + h[v] - h[u] < dist[u]:
						dist[u] = dist[v] + cost + h[v] - h[u]
						prevv[u] = v
						preve[u] = edge
						heapq.heappush(heap, (dist[u], u))
			if dist[to_v] == float('inf'):
				return -1
			for (i, d) in enumerate(dist):
				h[i] += d
			flow = remains
			v = to_v
			while v != from_v:
				cap = preve[v][1]
				flow = min(cap, flow)
				v = prevv[v]
			v = to_v
			while v != from_v:
				preve[v][1] -= flow
				preve[v][3][1] += flow
				v = prevv[v]
			remains -= flow
			res += flow * h[to_v]
		return res
(V, E, F) = list(map(int, sys.stdin.readline().split()))
UVCD = [list(map(int, sys.stdin.readline().split())) for _ in range(E)]
graph = [[] for _ in range(V)]
for (u, v, c, d) in UVCD:
	graph[u].append((v, c, d))
ans = MinCostFlow(graph=graph).solve(from_v=0, to_v=V - 1, flow=F)
print(ans)


import heapq
INF = 10 ** 5

class MinCostFlow:

	def __init__(self, V):
		self.V = V
		self.G = [[] for _ in range(V)]
		self.prevv = [INF] * V
		self.preve = [INF] * V
		self.h = [0] * V

	def add_edge(self, from_, to_, cap, cost):
		self.G[from_].append([to_, cap, cost, len(self.G[to_])])
		self.G[to_].append([from_, 0, -cost, len(self.G[from_]) - 1])

	def _get_dist(self, s, t, f):
		d = f
		v = t
		while v != s:
			pre_v = self.prevv[v]
			pre_edge = self.preve[v]
			d = min(d, self.G[pre_v][pre_edge][1])
			v = pre_v
		return d

	def _update_cap(self, s, t, d):
		v = t
		while v != s:
			pre_v = self.prevv[v]
			pre_e = self.preve[v]
			e = self.G[pre_v][pre_e]
			e[1] -= d
			rev = e[3]
			self.G[v][rev][1] += d
			v = pre_v

	def solve(self, s, t, f):
		res = 0
		self.h = [0] * self.V
		dist = [INF] * self.V
		while f > 0:
			que = []
			for i in range(self.V):
				dist[i] = INF
			dist[s] = 0
			heapq.heappush(que, (0, s))
			while que:
				p = heapq.heappop(que)
				v = p[1]
				if dist[v] < p[0]:
					continue
				for i in range(len(self.G[v])):
					e = self.G[v][i]
					to_ = e[0]
					cap = e[1]
					cost = e[2]
					if cap <= 0:
						continue
					if dist[to_] > dist[v] + cost + self.h[v] - self.h[to_]:
						dist[to_] = dist[v] + cost + self.h[v] - self.h[to_]
						self.prevv[to_] = v
						self.preve[to_] = i
						heapq.heappush(que, (dist[to_], to_))
			if dist[t] == INF:
				return -1
			for v in range(self.V):
				self.h[v] += dist[v]
			d = self._get_dist(s, t, f)
			res += d * self.h[t]
			f -= d
			self._update_cap(s, t, d)
		return res
(v, e, f) = [int(_) for _ in input().split()]
mcf = MinCostFlow(v)
for i in range(e):
	mcf.add_edge(*[int(_) for _ in input().split()])
print(mcf.solve(0, v - 1, f))


import sys
readline = sys.stdin.readline
from heapq import heappop as hpp, heappush as hp

class MinCostFlowwithDijkstra:
	INF = 1 << 31

	def __init__(self, N):
		self.N = N
		self.Edge = [[] for _ in range(N)]

	def add_edge(self, st, en, cap, cost):
		self.Edge[st].append([en, cap, cost, len(self.Edge[en])])
		self.Edge[en].append([st, 0, -cost, len(self.Edge[st]) - 1])

	def get_mf(self, so, si, fl):
		N = self.N
		INF = self.INF
		res = 0
		Pot = [0] * N
		geta = N
		prv = [None] * N
		prenum = [None] * N
		while fl:
			dist = [INF] * N
			dist[so] = 0
			Q = [so]
			while Q:
				(cost, vn) = divmod(hpp(Q), geta)
				if dist[vn] < cost:
					continue
				for enum in range(len(self.Edge[vn])):
					(vf, cap, cost, _) = self.Edge[vn][enum]
					cc = dist[vn] + cost - Pot[vn] + Pot[vf]
					if cap > 0 and dist[vf] > cc:
						dist[vf] = cc
						prv[vf] = vn
						prenum[vf] = enum
						hp(Q, cc * geta + vf)
			if dist[si] == INF:
				return -1
			for i in range(N):
				Pot[i] -= dist[i]
			cfl = fl
			vf = si
			while vf != so:
				cfl = min(cfl, self.Edge[prv[vf]][prenum[vf]][1])
				vf = prv[vf]
			fl -= cfl
			res -= cfl * Pot[si]
			vf = si
			while vf != so:
				e = self.Edge[prv[vf]][prenum[vf]]
				e[1] -= cfl
				self.Edge[vf][e[3]][1] += cfl
				vf = prv[vf]
		return res
(N, M, F) = map(int, readline().split())
T = MinCostFlowwithDijkstra(N)
for _ in range(M):
	(u, v, cap, cost) = map(int, readline().split())
	T.add_edge(u, v, cap, cost)
print(T.get_mf(0, N - 1, F))


import heapq

class edge:

	def __init__(self, to, cap, cost, rev):
		self.to: int = to
		self.cap: int = cap
		self.cost: int = cost
		self.rev: int = rev

class min_cost_flow:

	def __init__(self, N):
		self.N: int = N
		self.INF: int = 1000000000000000000
		self.G = [[] for i in range(N)]

	def add_edge(self, fro, to, cap, cost):
		self.G[fro].append(edge(to, cap, int(cost), int(len(self.G[to]))))
		self.G[to].append(edge(fro, 0, -int(cost), int(len(self.G[fro]) - 1)))

	def solve(self, s, t, f):
		N = self.N
		prevv = [0 for i in range(N)]
		preve = [0 for i in range(N)]
		ret = 0
		while 0 < f:
			dist = [self.INF for i in range(N)]
			dist[s] = 0
			hq = [(0, s)]
			heapq.heapify(hq)
			while hq:
				(d, v) = heapq.heappop(hq)
				for i in range(len(self.G[v])):
					e = self.G[v][i]
					if 0 < e.cap and dist[v] + e.cost < dist[e.to]:
						dist[e.to] = dist[v] + e.cost
						prevv[e.to] = v
						preve[e.to] = i
						heapq.heappush(hq, (dist[e.to], e.to))
			if dist[t] == self.INF:
				return self.INF
			d = f
			v = t
			while v != s:
				d = min(d, self.G[prevv[v]][preve[v]].cap)
				v = prevv[v]
			f -= d
			ret += d * dist[t]
			v = t
			while v != s:
				e = self.G[prevv[v]][preve[v]]
				e.cap -= d
				self.G[v][e.rev].cap += d
				v = prevv[v]
		return ret
(v, e, f) = map(int, input().split())
mcf = min_cost_flow(v)
for i in range(e):
	(ui, vi, ci, di) = map(int, input().split())
	mcf.add_edge(ui, vi, ci, di)
ans = mcf.solve(0, v - 1, f)
if ans == mcf.INF:
	print(-1)
else:
	print(ans)


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
(n, m, f) = map(int, input().split())
edges = [[] for _ in range(n)]
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))


from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

def LI():
	return list(map(int, sys.stdin.readline().split()))

def I():
	return int(sys.stdin.readline())

def LS():
	return list(map(list, sys.stdin.readline().split()))

def S():
	return list(sys.stdin.readline())[:-1]

def IR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = I()
	return l

def LIR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = LI()
	return l

def SR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = S()
	return l

def LSR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = SR()
	return l
mod = 1000000007

def dijkstra(s, h):
	dist = [float('inf')] * n
	prev = [-1] * n
	dist[s] = 0
	q = [(0, s)]
	while q:
		(dx, x) = heappop(q)
		for y in v[x]:
			if cap[x][y] <= 0:
				continue
			dy = dx + cost[x][y] + h[x] - h[y]
			if dy < dist[y]:
				dist[y] = dy
				prev[y] = x
				heappush(q, (dy, y))
	return (dist, prev)

def minimim_flow(s, g, f):
	res = 0
	h = [0] * n
	while f > 0:
		(dist, prev) = dijkstra(s, h)
		if dist[g] == float('inf'):
			return -1
		for i in range(n):
			h[i] += dist[i]
		flow = f
		y = g
		while y != s:
			x = prev[y]
			if cap[x][y] < flow:
				flow = cap[x][y]
			y = x
		f -= flow
		res += flow * h[g]
		y = g
		while y != s:
			x = prev[y]
			cap[x][y] -= flow
			cap[y][x] += flow
			y = x
	return res
(n, m, f) = LI()
v = [[] for i in range(n)]
cap = [defaultdict(lambda : 0) for i in range(n)]
cost = [defaultdict(lambda : 0) for i in range(n)]
for i in range(m):
	(a, b, c, d) = LI()
	v[a].append(b)
	v[b].append(a)
	cost[a][b] = d
	cost[b][a] = -d
	cap[a][b] = c
print(minimim_flow(0, n - 1, f))


from heapq import heappush, heappop
import collections

class MinCostFlowDijkstra:

	def __init__(self, N):
		self.N = N
		self.edges = collections.defaultdict(list)

	def add(self, fro, to, cap, cost, directed=True):
		if directed:
			self.edges[fro].append([to, cap, cost, len(self.edges[to])])
			self.edges[to].append([fro, 0, -cost, len(self.edges[fro]) - 1])
		else:
			self.edges[fro].append([to, cap, cost, len(self.edges[to])])
			self.edges[to].append([fro, 0, -cost, len(self.edges[fro]) - 1])
			self.edges[to].append([fro, cap, cost, len(self.edges[fro])])
			self.edges[fro].append([to, 0, -cost, len(self.edges[to]) - 1])

	def minCostFlow(self, start, goal, flow):
		res = 0
		potential = collections.defaultdict(int)
		prevVertex = collections.defaultdict(int)
		prevEdge = collections.defaultdict(int)
		while flow > 0:
			dist = collections.defaultdict(lambda : float('inf'))
			dist[start] = 0
			que = []
			heappush(que, (0, start))
			while que:
				(k, v) = heappop(que)
				if dist[v] < k:
					continue
				for (i, (to, cap, cost, _)) in enumerate(self.edges[v]):
					if cap > 0 and dist[to] > dist[v] + cost + potential[v] - potential[to]:
						dist[to] = dist[v] + cost + potential[v] - potential[to]
						prevVertex[to] = v
						prevEdge[to] = i
						heappush(que, (dist[to], to))
			if dist[goal] == float('inf'):
				return -1
			for i in range(self.N):
				potential[i] += dist[i]
			d = flow
			v = goal
			while v != start:
				d = min(d, self.edges[prevVertex[v]][prevEdge[v]][1])
				v = prevVertex[v]
			flow -= d
			res += d * potential[goal]
			v = goal
			while v != start:
				e = self.edges[prevVertex[v]][prevEdge[v]]
				e[1] -= d
				self.edges[v][e[3]][1] += d
				v = prevVertex[v]
		return res
(V, E, F) = map(int, input().split())
graph = MinCostFlowDijkstra(V)
for _ in range(E):
	(u, v, c, d) = map(int, input().split())
	graph.add(u, v, c, d)
print(graph.minCostFlow(0, V - 1, F))


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
import time, random
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
mod2 = 998244353
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

class Edge:

	def __init__(self, t, f, r, ca, co):
		self.to = t
		self.fron = f
		self.rev = r
		self.cap = ca
		self.cost = co

class MinCostFlow:
	size = 0
	graph = []

	def __init__(self, s):
		self.size = s
		self.graph = [[] for _ in range(s)]

	def add_edge(self, f, t, ca, co):
		self.graph[f].append(Edge(t, f, len(self.graph[t]), ca, co))
		self.graph[t].append(Edge(f, t, len(self.graph[f]) - 1, 0, -co))

	def min_path(self, s, t):
		dist = [inf] * self.size
		route = [None] * self.size
		que = collections.deque()
		inq = [False] * self.size
		dist[s] = 0
		que.append(s)
		inq[s] = True
		while que:
			u = que.popleft()
			inq[u] = False
			for e in self.graph[u]:
				if e.cap == 0:
					continue
				v = e.to
				if dist[v] > dist[u] + e.cost:
					dist[v] = dist[u] + e.cost
					route[v] = e
					if not inq[v]:
						que.append(v)
						inq[v] = True
		if dist[t] == inf:
			return (inf, 0)
		flow = inf
		v = t
		while v != s:
			e = route[v]
			if flow > e.cap:
				flow = e.cap
			v = e.fron
		c = 0
		v = t
		while v != s:
			e = route[v]
			e.cap -= flow
			self.graph[e.to][e.rev].cap += flow
			c += e.cost * flow
			v = e.fron
		return (dist[t], flow)

	def calc_min_cost_flow(self, s, t, flow):
		total_cost = 0
		while flow > 0:
			(c, f) = self.min_path(s, t)
			if f == 0:
				return inf
			f = min(flow, f)
			total_cost += c * f
			flow -= f
		return total_cost

def main():
	(n, m, f) = LI()
	uvcd = [LI() for _ in range(m)]
	mf = MinCostFlow(n)
	for (u, v, c, d) in uvcd:
		mf.add_edge(u, v, c, d)
	r = mf.calc_min_cost_flow(0, n - 1, f)
	if r == inf:
		return -1
	return r
print(main())