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

Solution:
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
//#include "MyMath.h"
//#include "MyDisjointset.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
#include <stdio.h>
#include <math.h>
#include <string.h>
using namespace std;
typedef pair<int, int> P; typedef long long int ll; typedef vector <int> vecint; typedef vector <vecint> dvecint; typedef vector <dvecint> vecdvecint; typedef vector <vector <dvecint> > dvecdvecint;
const ll INF = 2000000000;
struct edge {
	int to, cap, cost, rev;
	edge(int t, int ca, int co, int re) {
		to = t;
		cap = ca;
		cost = co;
		rev = re;
	}
};
vector <edge> G[100];
int prv[100], pre[100], d[100];
int v, e, flow;
void addedge(int from, int to, int cap, int cost) {
	G[from].push_back(edge(to, cap, cost, G[to].size()));
	G[to].push_back(edge(from, 0, -cost, G[from].size() - 1));
}
int minimumcost(int s, int t, int f) {
	int res = 0;
	while (f > 0) {
		fill(d, d + v, INF);
		d[s] = 0;
		bool ud = true;
		while (ud) {
			ud = false;
			for (int i = 0; i < v; i++) {
				if (d[i] == INF) continue;
				for (int j = 0; j < G[i].size(); j++) {
					edge &e = G[i][j];
					if (e.cap > 0 && d[e.to] > d[i] + e.cost) {
						d[e.to] = d[i] + e.cost;
						prv[e.to] = i;
						pre[e.to] = j;
						ud = true;
					}
				}
			}
		}
		if (d[t] == INF) return -1;
		int dis = f;
		for (int w = t; w != s; w = prv[w]) {
			dis = min(dis, G[prv[w]][pre[w]].cap);
		}
		f -= dis;
		for (int w = t; w != s; w = prv[w]) {
			G[prv[w]][pre[w]].cap -= dis;
			G[w][G[prv[w]][pre[w]].rev].cap += dis;
		}
		res += dis * d[t];
	}
	return res;
}
int main() {
	cin >> v >> e >> flow;
	for (int i = 0; i < e; i++) {
		int s, t, c, d; cin >> s >> t >> c >> d;
		addedge(s, t, c, d);
	}
	cout << minimumcost(0, v - 1, flow) << endl;
	return 0;
}