#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
const int MAXN=5e4+5,oo=0x3f3f3f3f;
int n,m,k,s,t,h[MAXN],ec=1,ans,sum;
struct Edge{
	int u,v,w,c,nxt;
}e[MAXN<<2];
inline void AddEdge(int u,int v,int w,int c)
{
	e[++ec]={u,v,w,c,h[u]};
	h[u]=ec;
}
inline void Add(int u,int v,int w,int c)
{
	AddEdge(u,v,w,c);
	AddEdge(v,u,0,-c);
}
int vis[MAXN],dis[MAXN];
queue<int>que;
bool SPFA(int s,int t){ 
	while(!que.empty())que.pop();
	memset(vis,0,sizeof vis);
	memset(dis,0x3f,sizeof dis);
	vis[t]=1,que.push(t),dis[t]=0;
	while(!que.empty()){
		int u=que.front();que.pop();
		vis[u]=0;
		for(int i=h[u];i;i=e[i].nxt){
			if(e[i^1].w&&dis[u]+e[i^1].c<dis[e[i].v]){
				dis[e[i].v]=dis[u]+e[i^1].c;
				if(vis[e[i].v])continue;
				que.push(e[i].v);
				vis[e[i].v]=1;
			}
		}
	}
	return dis[s]!=oo;
} 
int DFS(int u, int t, int f){ 
	if(u==t||!f)return f;
	vis[u]=1;
	int rest=f;
	for(int i=h[u];i;i=e[i].nxt){
		if(dis[e[i].v]!=dis[u]-e[i].c||!e[i].w||vis[e[i].v])continue;
		int tmp=DFS(e[i].v,t,min(e[i].w,rest));
		if(!tmp){
			dis[e[i].v]=oo;
			continue;
		}
		e[i].w-=tmp;
		e[i^1].w+=tmp;
		rest-=tmp;
		if(!rest)return f;
	}
	vis[u]=0;
	return f-rest;
}
void ZKW(int s,int t){ 
	ans=sum=0;
	while(SPFA(s,t)){
		memset(vis,0,sizeof vis);
		int tmp=DFS(s,t,oo);
		ans+=tmp;sum+=tmp*dis[s];
	}
}
int main()
{
	while(~scanf("%d %d %d",&n,&m,&k)){
		memset(h,0,sizeof h);
		memset(e,0,sizeof e);
		ec=s=1,t=n;
		int S=0,T=n+1;
		for(int i=1,u,v,w,c;i<=m;i++)
		{
			scanf("%d %d %d %d",&u,&v,&c,&w);
			for(int j=1;j<=w;j++)Add(u,v,1,c*(j*2-1));
		}
		Add(S,s,k,0);
		Add(t,T,k,0);
		ZKW(S,T);
		if(ans>=k)printf("%d\n",sum);
		else puts("-1");
	}
	return 0;
}