#include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <queue>

 #include <vector>

 using namespace std;

 const int maxn =  + ;

 const int INF = 0x3f3f3f3f;

 struct Edge

 {

     int from, to, cap, flow, cost;

     Edge(int u, int v, int cap, int flow, int cost):from(u), to(v), cap(cap), flow(flow), cost(cost) {}

 };

 int n, s, t, m, k;

 vector<Edge> edges;

 vector<int> G[maxn];

 void init(int n)

 {

     for(int i = ; i < n; i++) G[i].clear();

     edges.clear();

 }

 void AddEdge(int u, int v, int cap, int cost)

 {

     edges.push_back(Edge(u, v, cap, , cost));

     edges.push_back(Edge(v, u, , , -cost));

     int m = edges.size();

     G[u].push_back(m - );

     G[v].push_back(m - );

 }

 bool inq[maxn];

 int p[maxn], d[maxn], a[maxn];

 bool SPFA()

 {

     memset(d, 0x3f, sizeof(d));

     d[s] = ;

     queue<int> Q;

     Q.push(s);

     memset(inq, false, sizeof(inq));

     inq[s] = true;

     memset(p, -, sizeof(p));

     a[s] = INF;

     while(!Q.empty())

     {

         int u = Q.front(); Q.pop(); inq[u] = false;

         for(int i = ; i < G[u].size(); i++)

         {

             Edge& e = edges[G[u][i]];

             int v = e.to;

             if(e.cap > e.flow && d[u] + e.cost < d[v])

             {

                 d[v] = d[u] + e.cost;

                 p[v] = G[u][i];

                 a[v] = min(a[u], e.cap - e.flow);

                 if(!inq[v]) { inq[v] = true; Q.push(v); }

             }

         }

     }

     return d[t] < INF;

 }

 int Maxf;

 int Mincost()

 {

     int cost = ;

     Maxf = ;

     while(SPFA())

     {

         Maxf += a[t];

         cost += a[t] * d[t];

         int u = t;

         while(u != s)

         {

             edges[p[u]].flow += a[t];

             edges[p[u]^].flow -= a[t];

             u = edges[p[u]].from;

         }

     }

     return cost;

 }

 int main()

 {

     while(scanf("%d%d%d", &n, &m, &k) == )

     {

         init(n + );

         s = , t = n;

         AddEdge(s, , k, );

         while(m--)

         {

             int u, v, a, C;

             scanf("%d%d%d%d", &u, &v, &a, &C);

             for(int i = ; i < C; i++)

                 AddEdge(u, v, , a * (i *  + ));

         }

         int cost = Mincost();

         if(Maxf < k) puts("-1");

         else printf("%d\n", cost);

     }

     return ;

 }