#include #include #include #include #include #include #include using namespace std; typedef long long ll; #define rep(i, n) for(int i = 0; i < (n); i++) template using vi = vector; template using vii = vector>; template using viii = vector>; struct FF { struct edge { int to, rev; ll cap; }; int n; vii to; vi visited; FF(int n_ = 1) : n(n_), to(n_){} void addedge(int u, int v, ll c) { int su = (int)to[u].size(); int sv = (int)to[v].size(); to[u].push_back({ v, sv, c }); to[v].push_back({ u, su, 0 }); } ll dfs(int v, int t, ll f = 1e18) { if (v == t) return f; visited[v] = true; for (edge& nv : to[v]) { if (visited[nv.to] || nv.cap == 0) continue; ll nf = dfs(nv.to, t, min(f, nv.cap)); if (nf > 0) { nv.cap -= nf; to[nv.to][nv.rev].cap += nf; return nf; } } return 0; //忘れがち } ll maxflow(int s, int t) { ll res = 0, flow = 0; do { visited.assign(n, false); flow = dfs(s, t); res += flow; } while (flow); return res; } }; int main() { int n, m, d; cin >> n >> m >> d; vi u(m), v(m), p(m), q(m); vi w(m); rep(i, m) cin >> u[i] >> v[i] >> p[i] >> q[i] >> w[i]; rep(i, m) u[i]--, v[i]--; rep(i, m) q[i] += d; vi> mp(n); rep(i, m) { mp[u[i]][p[i]]; mp[v[i]][q[i]]; } const int inf = 2e9; FF ff(n * m); int idx = 0; rep(i, n) { bool ng = true; for (auto& elem : mp[i]) { elem.second = idx; if (ng) ng = false; else ff.addedge(idx - 1, idx, inf); idx++; } } rep(i, m) ff.addedge(mp[u[i]][p[i]], mp[v[i]][q[i]], w[i]); ll res = ff.maxflow(0, idx - 1); cout << res << endl; return 0; }