Problem: 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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

struct edge {
  i64 from;
  i64 to;
  i64 cap;
  i64 cost;
  i64 rev;
};

i64 INF = 1e18;

i64 capacity_scaling_bflow(std::vector<std::vector<edge>>& g, std::vector<i64> b) {
  i64 ans = 0;


  i64 U = *std::max_element(begin(b), end(b));
  i64 delta = (1 << ((int)(std::log2(U)) + 1));
  int n = g.size();

  std::vector<i64> e = b;

  std::vector<i64> p(n, 0);

  int zero = 0;

  for(auto x : e) {
    if(x == 0) zero++;
  }

  for(;delta > 0; delta >>= 1) {
    if(zero == n) break;
    for(int s = 0;s < n;s++) {
      if(!(e[s] >= delta)) continue;
      std::vector<std::size_t> pv(n, -1);
      std::vector<std::size_t> pe(n, -1);
      std::vector<i64> dist(n, INF);
      using P = std::pair<i64,i64>;
      std::priority_queue<P,std::vector<P>,std::greater<P>> que;
      dist[s] = 0;
      que.push({dist[s], s});
      while(!que.empty()) {
        int v = que.top().second;
        i64 d = que.top().first;
        que.pop();
        if(dist[v] < d) continue;
        for(std::size_t i = 0;i < g[v].size();i++) {
          const auto& e = g[v][i];
          std::size_t u = e.to;
          if(e.cap == 0) continue;
          if(dist[u] > dist[v] + e.cost + p[v] - p[u]) {
            dist[u] = dist[v] + e.cost + p[v] - p[u];
            pv[u] = v;
            pe[u] = i;
            que.push({dist[u], u});
          }
        }
      }

      for(int i = 0;i < n;i++) {
        if(pv[i] != -1) p[i] += dist[i];
      }

      int t = 0;
      for(;t < n;t++) {
        if(!(e[s] >= delta)) break;
        if(e[t] <= -delta && pv[t] != -1) {
          std::size_t u = t;
          for(;pv[u] != -1;u = pv[u]) {
            ans += delta * g[pv[u]][pe[u]].cost;
            g[pv[u]][pe[u]].cap -= delta;
            g[u][g[pv[u]][pe[u]].rev].cap += delta;
          }
          e[u] -= delta;
          e[t] += delta;
          if(e[u] == 0) zero++;
          if(e[t] == 0) zero++;
        }
      }
    }
  }
  
  if(zero == n) return ans;
  else return -1e18;
}

int main() {
  i64 N,M,F;
  cin >> N >> M >> F;
  vector<vector<edge>> g(N + M);
  vector<i64> e(N + M, 0);
  int s = 0;
  int t = N - 1;
  e[s + M] = F;
  e[t + M] = -F;
  for(int i = 0;i < M;i++) {
    i64 a,b,c,d;
    cin >> a >> b >> c >> d;

    e[i] = c;
    e[a + M] -= c;

    g[i].push_back({i, a + M, (i64)1e18, 0, (i64)g[a + M].size()});
    g[a + M].push_back({a + M, i, 0, 0, (i64)g[i].size() - 1});

    g[i].push_back({i, b + M, (i64)1e18, d, (i64)g[b + M].size()});
    g[b + M].push_back({b + M, i, 0, -d, (i64)g[i].size() - 1});
  }


  i64 ans = capacity_scaling_bflow(g, e);
  if(ans == -1e18) {
    cout << -1 << endl;
  }
  else {
    cout << ans << endl;
  }
}