#include using namespace std; template struct Dinic { static const int MAXV = 10000; T INF = inf; struct Edge { int v; T f; int re; Edge(int _v, T _f, int _re) : v(_v), f(_f), re(_re) {} }; int n, s, t, level[MAXV]; vector E[MAXV]; int now[MAXV]; Dinic(int _n, int _s, int _t) : n(_n), s(_s), t(_t) {} void add_edge(int u, int v, T f, bool bidirectional = false) { E[u].emplace_back(v, f, E[v].size()); E[v].emplace_back(u, 0, E[u].size() - 1); if (bidirectional) { E[v].emplace_back(u, f, E[u].size() - 1); } } bool BFS() { memset(level, -1, sizeof(level)); queue que; que.emplace(s); level[s] = 0; while (que.size()) { int u = que.front(); que.pop(); for (auto it : E[u]) { if (it.f > 0 && level[it.v] == -1) { level[it.v] = level[u] + 1; que.emplace(it.v); } } } return level[t] != -1; } T DFS(int u, T nf) { if (u == t) return nf; T res = 0; while (now[u] < E[u].size()) { Edge &it = E[u][now[u]]; if (it.f > 0 && level[it.v] == level[u] + 1) { T tf = DFS(it.v, min(nf, it.f)); res += tf; nf -= tf; it.f -= tf; E[it.v][it.re].f += tf; if (nf == 0) return res; } else ++now[u]; } if (!res) level[u] = -1; return res; } T flow(T res = 0) { while (BFS()) { T temp; memset(now, 0, sizeof(now)); while (temp = DFS(s, INF)) { res += temp; res = min(res, INF); } } return res; } }; signed main() { ios::sync_with_stdio(false); int N, M, D; cin >> N >> M >> D; vector U(M), V(M), P(M), Q(M), W(M); map, int> id; id[make_pair(0, 0)] = 0; id[make_pair(N - 1, int(2e9))] = 1; for (int i = 0; i < M; ++i) { cin >> U[i] >> V[i] >> P[i] >> Q[i] >> W[i]; --U[i]; --V[i]; if (!id.count(make_pair(U[i], P[i]))) { int x = id.size(); id[make_pair(U[i], P[i])] = x; } if (!id.count(make_pair(V[i], Q[i] + D))) { int x = id.size(); id[make_pair(V[i], Q[i] + D)] = x; } } Dinic din(id.size(), 0, 1); for (auto it = id.begin(); it != id.end(); ++it) { for (auto jt = next(it); jt != id.end(); ++jt) { if ((it->first).first == (jt->first).first) { int x = it->second; int y = jt->second; if ((it->first).second > (jt->first).second) { swap(x, y); } din.add_edge(x, y, din.INF); } } } for (int i = 0; i < M; ++i) { int x = id[make_pair(U[i], P[i])]; int y = id[make_pair(V[i], Q[i] + D)]; din.add_edge(x, y, W[i]); } cout << din.flow() << endl; return 0; }