// STLのインクルード #include using namespace std; // // ACLのインクルード(デフォルトはコメントアウト) // #include // using namespace atcoder; // for文の略記 #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define per(i, n) for (ll i = (ll)(n-1); i >= 0; i--) // vectorのソート #define all(x) x.begin(), x.end() // 型の略記 (競プロならでは) using ll = long long; using pii = pair; using pll = pair; using vi = vector; using vl = vector; using vs = vector; using vc = vector; using vpii = vector>; using vpll = vector>; using vpsi = vector>; using vvi = vector>; using vvpii = vector>>; using vvl = vector>; using vvc = vector>; template using priority_queue_up = priority_queue, greater>; // MOD計算で使う #define MOD 1000000007 #define MOD2 998244353 // YES-NOで答える質問で使う(fがTrueならYes) void cout_yn(bool f){ if(f)cout << "Yes" << endl; else cout << "No" << endl; } // 木の前順走査 void dfs_preorder(ll v, vvi &tree, vi &output){ output.push_back(v); rep(i, tree[v].size()){ dfs_preorder(tree[v][i], tree, output); } } // 木の後順走査 void dfs_postorder(ll v, vvi &tree, vi &output){ rep(i, tree[v].size()){ dfs_preorder(tree[v][i], tree, output); } output.push_back(v); } // n頂点m辺の無向グラフを隣接リストで受け取る. // 頂点番号は1-indexedとして入力される想定. vector> input_undir_graph(ll n, ll m){ ll a, b; vector> g(n); rep(i, m){ cin >> a >> b; a--, b--; g[a].push_back(b); // a->b へ向かう辺 g[b].push_back(a); // b->a へ向かう辺 } return g; } // n頂点m辺の有向グラフを隣接リストで受け取る. // 頂点番号は1-indexedとして入力される想定. vector> input_dir_graph(ll n, ll m){ ll a, b; vector> g(n); rep(i, m){ cin >> a >> b; a--, b--; g[a].push_back(b); // a->b へ向かう辺 } return g; } #define INF 1e10 struct edge{ ll to, cap, q, rev; }; map>> G; vector> used; ll n, m; ll d; void add_edge(ll u, ll v, ll c, ll p, ll q){ if(G[p].size() == 0)G[p].resize(n); if(G[q].size() == 0)G[q].resize(n); G[p][u].push_back((edge){v, c, q, (ll)(G[q][v].size())}); G[q][v].push_back((edge){u, 0, p, (ll)(G[p][u].size()-1)}); } ll dfs(ll v, ll p, ll t, ll tq, ll f){ if(v == t && p == tq){ return f; } used[v][p] = 1; vector &E = G[p][v]; rep(i, E.size()){ edge &e = E[i]; if(e.cap > 0 && !used[e.to][e.q]){ ll w = dfs(e.to, e.q, t, tq, min(f, e.cap)); if(w > 0){ E[i].cap -= w; G[e.q][e.to][e.rev].cap += w; return w; } } } return 0; } ll max_flow(ll s, ll p, ll t, ll tq){ ll flow = 0; for(;;){ for(ll i=0; i> n >> m >> d; vector> time(n); used.resize(n); ll u, v, p, q, w; rep(i, m){ cin >> u >> v >> p >> q >> w; u--, v--; add_edge(u, v, w, p, q+d); time[u].insert(p); time[v].insert(q+d); } rep(i, n){ for(auto itr=time[i].begin(); itr!=--(time[i].end()); itr++){ auto nx = itr; ++nx; add_edge(i, i, INF, *itr, *nx); } } cout << max_flow(0, *time[0].begin(), n-1, *(--(time[n-1].end()))) << endl; return 0; }