#include <iostream>
#include <iomanip>
#include <climits>
#include <limits>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <functional>
#include <numeric>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <unordered_map>
#include <random>
#define _USE_MATH_DEFINES
#include <cmath>
#include <complex>

using namespace std;

typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;

const int INFL = (int)1e9;
const ll INFLL = (ll)1e18;
const double INFD = numeric_limits<double>::infinity();
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loopll(i, n) for(ll i = 0; i < (ll)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopll1(i, n) for(ll i = 1; i <= (ll)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define Looprll(i, n) for(ll i = (ll)n - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = (int)n; i >= 1; i--)
#define Looprll1(i, n) for(ll i = (ll)n; i >= 1; i--)
#define Loopitr(itr, container) for(auto itr = container.begin(); itr != container.end(); itr++)
#define printv(vector) Loop(i, vector.size()) { cout << vector[i] << " "; } cout << endl;
#define rnd(d) (ll)((double)d + (d >= 0 ? 0.5 : -0.5))
#define floorsqrt(x) ((ll)sqrt((double)x) + ((ll)sqrt((double)x) * (ll)sqrt((double)x) <= (ll)x ? 0 : -1))
#define ceilsqrt(x) ((ll)sqrt((double)x) + ((ll)x <= (ll)sqrt((double)x) * (ll)sqrt((double)x) ? 0 : 1))
#define ceildiv(a, b) ((ll)a / (ll)b + ((ll)a % (ll)b == 0 ? 0 : 1))
#define bitmanip(m,val) static_cast<bitset<(int)m>>(val)

/*******************************************************/

struct graph_t {
  int n;           // |V|, index begins with 0
  int m;           // |E|
  vector<P> edges; // E
  vector<ll> cost; // cost or distance
  vector<ll> cap;  // capacity
};

class Mincostflow {
private:
  struct edgedata {
    int eid, from, to;
    ll cost, cap;
    edgedata* dual_p;
    bool operator<(const edgedata & another) const {
      return (cost != another.cost ? cost < another.cost : cap > another.cap);
    }
  };
  struct node {
    int id; bool done; edgedata* fromedge_p; list<edgedata> edges; ll d;
    bool operator<(const node & another) const {
      return !(d != another.d ? d < another.d : id < another.id);
    }
  };
  vector<node> nodes;
  int n, m;
  int source, sink;
  edgedata* empty_edge;
  bool decision;
public:
  Mincostflow(graph_t G, int s, int t, ll flow) {
    n = G.n;
    m = G.m;
    nodes.resize(n);
    empty_edge = new edgedata;
    Loop(i, n) nodes[i] = { i, false, empty_edge,{}, LLONG_MAX };
    Loop(i, G.edges.size()) {
      int a = G.edges[i].first;
      int b = G.edges[i].second;
      nodes[a].edges.push_back({ i, a, b, G.cost[i], G.cap[i], empty_edge });
      nodes[b].edges.push_back({ i - m, b, a, -1 * G.cost[i], 0, &(nodes[a].edges.back()) });
      nodes[a].edges.back().dual_p = &(nodes[b].edges.back());
    }
    source = s;
    sink = t;
    Loop(i, n) nodes[i].edges.sort();
    ll df;
    ll sumf = 0;
    while (1) {
      Loop(i, n) {
        nodes[i].d = LLONG_MAX;
        nodes[i].fromedge_p = empty_edge;
      }
      nodes[source].d = 0;
      Loop(k, n) {
        Loop(i, n) {
          node *a = &nodes[i];
          for (auto itr = a->edges.begin(); itr != a->edges.end(); ++itr) {
            if (itr->cap == 0) continue;
            node *b = &nodes[itr->to];
            if (a->d != LLONG_MAX && a->d + itr->cost < b->d) {
              if (k == n - 1) { decision = false; return; }
              b->d = a->d + itr->cost;
              b->fromedge_p = &(*itr);
            }
          }
        }
      }
      if (nodes[sink].d == LLONG_MAX) break;
      df = LLONG_MAX;
      int focus = sink;
      while (focus != source) {
        df = min(df, nodes[focus].fromedge_p->cap);
        focus = nodes[focus].fromedge_p->from;
      }
      df = min(df, flow - sumf);
      focus = sink;
      while (focus != source) {
        nodes[focus].fromedge_p->cap -= df;
        nodes[focus].fromedge_p->dual_p->cap += df;
        focus = nodes[focus].fromedge_p->from;
      }
      sumf += df;
      if (sumf == flow) { decision = true; return; }
    }
    decision = false; return;
  }
  vll get_eid_flow() {
    if (!decision) return{};
    vll ret(m);
    Loop(i, n) {
      for (auto itr = nodes[i].edges.begin(); itr != nodes[i].edges.end(); ++itr) {
        if (itr->eid < 0) ret[itr->eid + m] = itr->cap;
      }
    }
    return ret;
  }
  ll get_cost() {
    if (!decision) return -1;
    ll ret = 0;
    Loop(i, n) {
      for (auto itr = nodes[i].edges.begin(); itr != nodes[i].edges.end(); ++itr) {
        if (itr->eid < 0) ret -= itr->cost * itr->cap;
      }
    }
    return ret;
  }
  ll get_maxflow() {
    ll ret = 0;
    for (auto itr = nodes[sink].edges.begin(); itr != nodes[sink].edges.end(); ++itr) {
      if (itr->eid < 0) ret += itr->cap;
    }
    return ret;
  }
};

int main() {
  graph_t G;
  ll f;
  cin >> G.n >> G.m >> f;
  Loop(i, G.m) {
    int s, t, c, d; cin >> s >> t >> c >> d;
    G.edges.push_back({ s, t });
    G.cap.push_back(c);
    G.cost.push_back(d);
  }
  Mincostflow mcf(G, 0, G.n - 1, f);
  ll ans = mcf.get_cost();
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3344