Examples

Input

4 5 2
0 1 2 1
0 2 1 2
1 2 1 1
1 3 1 3
2 3 2 1


Output

6


Input




Output
#include <bits/stdc++.h>
using namespace std;

struct SuccessiveShortestPath {
  struct Edge{ int to, cap, cost, rev; };
  int n, init;
  vector<vector<Edge>> g;
  vector<int> dist, pv, pe, h;

  SuccessiveShortestPath() {}
  SuccessiveShortestPath(int n, int INF = 1e9)
    : n(n), g(n), init(INF), dist(n), pv(n), pe(n) {}

  void addEdge(int u, int v, int cap, int cost) {
    int szU = g[u].size();
    int szV = g[v].size();
    g[u].push_back({v, cap, cost, szV});
    g[v].push_back({u, 0, -cost, szU - 1});
  }
  int dijkstra(int s, int t) {
    dist = vector<int>(n, init);
    using Node = pair<int, int>;
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    pq.push({dist[s] = 0, s});

    while (!pq.empty()) {
      auto d = pq.top().first;
      auto u = pq.top().second;
      pq.pop();
      if (dist[u] < d) continue;
      for (int i = 0; i < g[u].size(); ++i) {
        Edge& e = g[u][i];
        int v = e.to;
        if (e.cap > 0 && dist[v] > dist[u] + e.cost + h[u] - h[v]) {
          dist[v] = dist[u] + e.cost + h[u] - h[v];
          pv[v] = u;
          pe[v] = i;
          pq.push({dist[v], v});
        }
      }
    }
    return dist[t];
  }
  int build(int s, int t, int f) {
    int res = 0;
    h = vector<int>(n, 0);
    while (f > 0) {
      if (dijkstra(s, t) == init) return -1;
      for (int i = 0; i < n; ++i) h[i] += dist[i];
      int flow = f;
      for (int u = t; u != s; u = pv[u]) {
        flow = min(flow, g[pv[u]][pe[u]].cap);
      }
      f -= flow;
      res += flow * h[t];
      for (int u = t; u != s; u = pv[u]) {
        Edge& e = g[pv[u]][pe[u]];
        e.cap -= flow;
        g[u][e.rev].cap += flow;
      }
    }
    return res;
  }
};

int main() {
  int n, m, f; cin >> n >> m >> f;
  SuccessiveShortestPath ssp(n);
  while (m--) {
    int u, v, c, d; cin >> u >> v >> c >> d;
    ssp.addEdge(u, v, c, d);
  }
  cout << ssp.build(0, n - 1, f) << endl;
  return 0;
}

