#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>
using namespace std;
const int maxm = 50000*4;
const int maxn = 110;
struct node
{
int v,cost,flow,next;//v表示指向的下一个顶点,a表示系数,flow表示可以过的流量
}edge[maxm];
int head[maxn],dis[maxn],pre[maxn],cur[maxn],vis[maxn],aug[maxn];
int s,t,v,n,m,k,id,flow;
void add_edge(int u,int v,int flow,int cost){
edge[id].v = v;edge[id].cost = cost;edge[id].flow = flow;edge[id].next = head[u];head[u] = id++;
edge[id].v = u;edge[id].cost = -cost;edge[id].flow = 0;edge[id].next = head[v];head[v] = id++;
}
int min(int x,int y){
return x < y ? x : y;
}
void init(){
s = 0,t = n+1;
memset(head,-1,sizeof(head));id = 0;
int u,v,a,flow; while( m-- ){
scanf("%d%d%d%d",&u,&v,&a,&flow);
for(int i = 1; i <= flow; i++)//因为边很少,所以可以拆边
add_edge(u,v,1,i*i*a - a*(i-1)*(i-1));//每增加一条边,费用增加
}
//源点流出的流量为k,汇点流入的流量为k
add_edge(0,1,k,0);
add_edge(n,n+1,k,0);
}
int spfa(){
memset(dis,-1,sizeof(dis));
memset(vis,0,sizeof(vis));
memset(aug,-1,sizeof(aug));
queue<int>que;
aug[s] = (1<<30) -1;
dis[s] = 0;vis[s] = 1;pre[s] = s;
que.push(s);
while( !que.empty()){
int u = que.front();
que.pop();
vis[u] = 0;
for(int id = head[u]; id != -1; id = edge[id].next)
{
int v = edge[id].v;
if( edge[id].flow > 0)
{
int MIN = min(aug[u],edge[id].flow);
if(dis[v] == -1 || dis[v] > dis[u] + edge[id].cost)
{
dis[v] = dis[u] + edge[id].cost;
pre[v] = u;cur[v] = id;
aug[v] = MIN;
// cout << v << " " << aug[v] << endl;
if(!vis[v] ){
vis[v] = 1;
que.push(v);
}
}
}
}
}
if( dis[t] == -1 )return 0;
return 1;
}
int get_max(){ int mincost = 0;
while(spfa() ){
mincost += dis[t];
k -= aug[t];
int now = t;
while( now != s){
edge[cur[now]].flow -= aug[t];
edge[cur[now]^1].flow += aug[t];
now = pre[now];
}
}
if(k > 0)return -1;
return mincost;
}
int main(){
// freopen("in.txt","r",stdin);
while(~scanf("%d%d%d",&n,&m,&k)){
init();
printf("%d\n",get_max());
}
return 0;
}