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:
bool debug=false;
#include <string.h>
#include <stdio.h>
#include <queue>
#include <vector>
#include <utility>
using namespace std;
#define F first
#define S second
#define PB push_back
const int INF=1e9+10;
const int N=1e2+10;
pair<int,int> graph[N][N];
pair<int,int> dis[N];
int from[N];
int n;
int min(int a,int b){return a>b?b:a;}
pair<int,int> mcmf(int s,int t){
	for(int i=1;i<n;i++)dis[i]={INF,0};
	dis[s]={0,INF};
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	pair<int,int> nxt;
	int temp;
	pq.push({0,s});
	from[s]=s;
	while(!pq.empty()){
		nxt=pq.top();
		pq.pop();
		if(debug)printf("nxt=%d %d\n",nxt.F,nxt.S);
		if(dis[nxt.S].F<nxt.F)continue;
		for(int i=0;i<n;i++)if(graph[nxt.S][i].S>0&&nxt.F+graph[nxt.S][i].F<dis[i].F){
			dis[i]={nxt.F+graph[nxt.S][i].F,min(dis[nxt.S].S,graph[nxt.S][i].S)};
			pq.push({dis[i].F,i});
			from[i]=nxt.S;
		}else if(debug)printf("graph[%d][%d]=%d %d\n",nxt.S,i,graph[nxt.S][i].F,graph[nxt.S][i].S);
	}
	if(dis[t].S==0)return {-1,-1};
	temp=t;
	while(temp!=s){
		graph[temp][from[temp]].S+=dis[t].S;
		graph[from[temp]][temp].S-=dis[t].S;
		temp=from[temp];
	}	
	graph[temp][from[temp]].S+=dis[t].S;
	graph[from[temp]][temp].S-=dis[t].S;
	return dis[t];
}

int main(){
	int l,r,cost,cap,m,ans=0,f;
	pair<int,int> temp;
	scanf("%d%d%d",&n,&m,&f);
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)graph[i][j]={INF,0};
	while(m--){
		scanf("%d%d%d%d",&l,&r,&cap,&cost);
		graph[l][r]={cost,cap};
		graph[r][l]={-cost,0};
	}
	while(f>0){
		temp=mcmf(0,n-1);
		if(debug)printf("f=%d temp=(%d,%d)\n",f,temp.F,temp.S);
		if(temp.S<=0){
			printf("-1\n");
			return 0;
		}
		if(temp.S>f){
			ans+=temp.F*f;
			f=0;
		}
		else{
			ans+=temp.F*temp.S;
			f-=temp.S;
		}
	}
	printf("%d\n",ans);
}