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<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i=0;i<((int)(n));i++)
#define reg(i,a,b) for(int i=((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define ireg(i,a,b) for(int i=((int)(b));i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int,int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))

struct edge{
	int to,p;
	lli cap,co;
};
int n;
vector<edge> vs[105];

int ds[105];
mp bf[105];
int inf=1e8;
lli mincof(int st,int gl,int gf){
	lli res=0;
	while(gf>0){
		rep(i,n)ds[i]=inf;
		ds[st]=0;
		for(;;){
			bool ud=false;
			rep(i,n){
				if(ds[i]==inf)continue;
				rep(j,vs[i].size()){
					edge e=vs[i][j];
					if(e.cap<=0)continue;
					if(ds[e.to]>ds[i]+e.co){
						ds[e.to]=ds[i]+e.co;
						bf[e.to]=mp(i,j);
						ud=true;
					}
				}
			}
			if(!ud)break;
		}
		if(ds[gl]==inf)return -1;
		
		//rep(i,n)printf("%d / %d .. %d (%d %d)\n",gf,i,ds[i],bf[i].fir,bf[i].sec);

		lli nf=gf;
		int no=gl;
		while(no!=st){
			int to=bf[no].fir;
			edge& be=vs[to][bf[no].sec];
			nf=min(nf,be.cap);
			no=to;
		}
		
		lli cs=0;
		no=gl;
		while(no!=st){
			int to=bf[no].fir;
			edge& be=vs[to][bf[no].sec];
			be.cap-=nf;
			cs+=be.co;
			vs[no][be.p].cap+=nf;
			no=to;
		}
		res+=cs*nf;
		gf-=nf;
	}
	return res;
}

int m,gf;
int main(void){
	scanf("%d%d%d",&n,&m,&gf);
	rep(i,m){
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		edge e;
		e.to=b; e.p=vs[b].size(); e.cap=c; e.co=d;
		vs[a].push_back(e);
		e.to=a; e.p=vs[a].size()-1; e.cap=0; e.co=-d;
		vs[b].push_back(e);
	}
	printf("%lld\n",mincof(0,n-1,gf));	
	return 0;
}