#include using namespace std; typedef long long ll; typedef unsigned long long ull; #define REP(i, n) for(int i=0; ibool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b; //// {行き先, 容量, 逆辺} //// {to, cap, rev} //// G[v][to] <-> G[to][rev] using Edge = tuple; vector G[MAX_V]; //// G に辺と逆辺を追加 void add_edge(int from, int to, ll cap){ G[from].push_back(Edge(to, cap, G[to].size())); G[to].push_back(Edge(from, 0, G[from].size()-1)); } //// 増加パスをdfsで探索 ll find_path(int v, int t, ll f, auto& used){ if(v == t) return f; used[v] = true; for(auto& [to, cap, rev] : G[v]){ if(!used[to] && cap > 0){ ll d = find_path(to, t, min(f, cap), used); if(d > 0){ cap -= d; get<1>(G[to][rev]) += d; return d; } } } return 0; } //// sからtへの最大流を求める ll max_flow(int s, int t){ ll flow = 0; while(1){ vector used(MAX_V); ll f = find_path(s, t, INF, used); if(f == 0) break; flow += f; } return flow; } int main(){ ll N, M, D; cin >> N >> M >> D; using T = tuple; vector X; REP(i,M){ ll u, v, p, q, w; //cin >> u >> v >> p >> q >> w; scanf("%lld %lld %lld %lld %lld", &u, &v, &p, &q, &w); u--, v--; X.push_back(T(u, v, p, q, w)); } vector> vertex(N); vertex[0].push_back(0); vertex[N-1].push_back(1000000000LL); for(auto& [u, v, p, q, w] : X){ vertex[u].push_back(p); vertex[v].push_back(q+D); } map pos2idx; ll cnt = 0; REP(v, N){ sort(vertex[v].begin(), vertex[v].end()); vertex[v].erase(unique(vertex[v].begin(), vertex[v].end()), vertex[v].end()); int size = vertex[v].size(); REP(i, size){ pos2idx[P(v, vertex[v][i])] = cnt++; } } for(auto& [u, v, p, q, w] : X){ auto v0 = pos2idx[P(u, p)]; auto v1 = pos2idx[P(v, q+D)]; add_edge(v0, v1, w); } REP(v, N){ int size = vertex[v].size(); REP(i, size-1){ auto v0 = pos2idx[P(v, vertex[v][i])]; auto v1 = pos2idx[P(v, vertex[v][i+1])]; add_edge(v0, v1, INF); } } ll ans = max_flow(0, cnt-1); cout << ans << endl; return 0; }