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

using namespace std;

#define INF (int)1e8
#define _INF (int)-1e8
#define INFLL (long long)1e15
#define _INFLL (long long)-1e15
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = (int)n; i >= 1; i--)
#define bitmanip(m,val) static_cast<bitset<(int)m>>(val)
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef pair<int, int> P;

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

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 Maxflow {
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:
  Maxflow(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;
  }
};

int main() {
  graph_t G;
  cin >> G.n >> G.m;
  ll f; cin >> f;
  Loop(i, G.m) {
    int u, v;
    ll c, d;
    cin >> u >> v >> c >> d;
    G.edges.push_back({ u, v });
    G.cap.push_back(c);
    G.cost.push_back(d);
  }
  Maxflow maxflow(G, 0, G.n - 1, f);
  cout << maxflow.get_cost() << endl;
  return 0;
}

Measured memory_bytes: 3340