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;
const int maxq=1005;

struct edge{int to,cap,cost,rev;};

int n,m,k;
int d[maxn];
int a[maxn];
int p1[maxn];
int p2[maxn];
bool inq[maxn];
vector<edge>G[maxn];

void add_edge(int u,int v,int c,int w) {
	G[u].pb(edge{v,c,w,int(G[v].size())});
	G[v].pb(edge{u,0,-w,int(G[u].size()-1)});
}

int mcmf(int s,int t) {
	int flow=0 , cost=0;
	while (1) {
		memset(d,0x3f,sizeof(d));
		d[s]=0; a[s]=max(0,k-flow);
		int qh=0,qt=0,q[maxq];
		q[qt++]=s; inq[s]=1;
		while (qh<qt) {
			int u=q[qh++];
			inq[u]=0;
			for (int i=0;i<G[u].size();i++) {
				edge e=G[u][i];
				if (d[e.to]>d[u]+e.cost && e.cap) {
					d[e.to]=d[u]+e.cost;
					a[e.to]=min(a[u],e.cap);
					p1[e.to]=u;
					p2[e.to]=i;
					if (!inq[e.to]) {
						q[qt++]=e.to;
						inq[e.to]=1;
					}
				}
			}
		}
		if (d[t]==INF || !a[t]) break;
		flow+=a[t];
		cost+=a[t]*d[t];
		for (int v=t,u=p1[t];v!=s;v=u,u=p1[u]) {
			int id=p2[v];
			G[u][id].cap-=a[t];
			id=G[u][id].rev;
			G[v][id].cap+=a[t];
		}
	}
	if (flow<k) return -1;
	else return cost;
}

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