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 <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
namespace MCF{
	const int MAXN=120;
	const int MAXM=2100;
	int to[MAXM];
	int next[MAXM];
	int first[MAXN];
	int c[MAXM];
	long long w[MAXM];
	long long pot[MAXN];
	int rev[MAXM];
	long long ijk[MAXN];
	int v[MAXN];
	long long toc;
	int tof;
	int n;
	int m;
	void init(int _n){
		n=_n;for(int i=0;i<n;i++)first[i]=-1;
	}
	void ae(int a,int b,int cap,int wei){
		next[m]=first[a];to[m]=b;first[a]=m;c[m]=cap;w[m]=wei;m++;
		next[m]=first[b];to[m]=a;first[b]=m;c[m]=0;w[m]=-wei;m++;
	}
	int solve(int s,int t,int flo){
		toc=tof=0;
		for(int i=0;i<n;i++)pot[i]=0;
		while(tof<flo){
			for(int i=0;i<n;i++)ijk[i]=9999999999999LL;
			for(int i=0;i<n;i++)v[i]=0;
			priority_queue<pair<long long,int> > Q;
			ijk[s]=0;
			Q.push(make_pair(0,s));
			while(Q.size()){
				long long cost=-Q.top().first;
				int at=Q.top().second;
				Q.pop();
				if(v[at])continue;
				v[at]=1;
				for(int i=first[at];~i;i=next[i]){
					int x=to[i];
					if(v[x]||ijk[x]<=ijk[at]+w[i]-pot[x]+pot[at])continue;
					if(c[i]==0)continue;
					ijk[x]=ijk[at]+w[i]-pot[x]+pot[at];
					rev[x]=i;
					Q.push(make_pair(-ijk[x],x));
				}
			}
			int flow=flo-tof;
			if(!v[t])return 0;
			int at=t;
			while(at!=s){
				flow=min(flow,c[rev[at]]);
				at=to[rev[at]^1];
			}
			at=t;
			tof+=flow;
			toc+=flow*(ijk[t]-pot[s]+pot[t]);
			at=t;
			while(at!=s){
				c[rev[at]]-=flow;
				c[rev[at]^1]+=flow;
				at=to[rev[at]^1];
			}
			for(int i=0;i<n;i++)pot[i]+=ijk[i];
		}
		return 1;
	}
}
int main(){
	int a,b,c;scanf("%d%d%d",&a,&b,&c);
	MCF::init(a);
	for(int i=0;i<b;i++){
		int p,q,r,s;scanf("%d%d%d%d",&p,&q,&r,&s);
		MCF::ae(p,q,r,s);
	}
	int res=MCF::solve(0,a-1,c);
	if(!res)printf("-1\n");
	else printf("%lld\n",MCF::toc);
}