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:
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=105;

struct Edge {
	int from,to,cap,flow,cost;
	Edge(int u,int v,int c,int f,int w):from(u),to(v),cap(c),flow(f),cost(w) {}
};

int n,m,tf;
vector<Edge>edges;
vector<int>G[maxn];
bool inq[maxn];
int d[maxn];
int a[maxn];
int p[maxn];


inline void addedge (int u,int v,int c,int w) {
	edges.pb(Edge(u,v,c,0,w));
	edges.pb(Edge(v,u,0,0,-w));
	int id=edges.size()-2;
	G[u].pb(id);
	G[v].pb(id+1);
}

inline bool spfa (int s,int t,int& flow,int& cost) {
	for (int i=0;i<n;i++) d[i]=INF;
	d[s]=0; inq[s]=1; a[s]=max(0,tf-flow);
	queue<int>q;
	q.push(s);
	while (q.size()) {
		int u=q.front(); q.pop();
		inq[u]=0;
		for (int id:G[u]) {
			Edge& e=edges[id];
			if (e.cap>e.flow && d[e.to]>d[u]+e.cost) {
				d[e.to]=d[u]+e.cost;
				p[e.to]=id;
				a[e.to]=min(a[u],e.cap-e.flow);
				if (!inq[e.to]) {inq[e.to]=1;q.push(e.to);}
			}
		}
	}
	if (d[t]==INF) return 0;
	flow+=a[t];
	cost+=d[t]*a[t];
	// cout<<flow<<' '<<cost<<'\n';
	for (int u=t;u!=s;u=edges[p[u]].from) {
		edges[p[u]].flow+=a[t];
		edges[p[u]^1].flow-=a[t];
	}
	return 1;
}

inline int mcmf (int s,int t) {
	int flow=0 , cost=0;
	while (spfa(s,t,flow,cost) && flow<tf);
	if (flow<tf) return -1;
	else return cost;
}

int main() {
	cin>>n>>m>>tf;
	for (int i=0;i<m;i++) {
		int u,v,c,w; cin>>u>>v>>c>>w;
		addedge(u,v,c,w);
	}
	cout<<mcmf(0,n-1)<<'\n';
}