#include using namespace std; #include #include using ll = long long; using ld = long double; using Graph = vector>; using vi = vector; using vl = vector; using vll = vector; using vb = vector; using vvi = vector; using vvl = vector; using vvb = vector; using vvvb = vector; using vvll = vector; using vvvll = vector; using vd = vector; using vvd = vector; using vvvd = vector; using vc = vector; using vvc = vector; using lll = __int128_t; using vs = vector; using pii = pair; const long double EPS = 1e-10; const double INF = 1e18; const long double PI = acos(-1.0L); #define mp make_pair #define reps(i, a, n) for (ll i = (a); i < (ll)(n); i++) #define rep(i, n) for (ll i = (0); i < (ll)(n); i++) #define rrep(i, n) for (ll i = (1); i < (ll)(n + 1); i++) #define repd(i, n) for (ll i = n - 1; i >= 0; i--) #define rrepd(i, n) for (ll i = n; i >= 1; i--) #define ALL(n) n.begin(), n.end() #define rALL(n) n.rbegin(), n.rend() #define fore(i, a) for (auto &i : a) #define IN(a, x, b) (a <= x && x < b) #define IN(a, x, b) (a <= x && x < b) #define INIT \ std::ios::sync_with_stdio(false); \ std::cin.tie(0); template inline T CHMAX(T &a, const T b) { return a = (a < b) ? b : a; } template inline T CHMIN(T &a, const T b) { return a = (a > b) ? b : a; } #include // min, max, swap, sort, reverse, lower_bound, upper_bound #include // bitset #include // isupper, islower, isdigit, toupper, tolower #include // int64_t, int*_t #include // printf #include // deque #include // cout, endl, cin #include // map #include // queue, priority_queue #include // set #include // stack #include // string, to_string, stoi #include // tuple, make_tuple #include // unordered_map #include // unordered_set #include // pair, make_pair #include // vector using namespace std; #include #define LOOP(n) REPI($_, (n)) #define REPI(i, n) \ for (int i = 0, i##_length = static_cast(n); i < i##_length; ++i) #define REPF(i, l, r) \ for (std::common_type_t i = (l), i##_last = (r); \ i < i##_last; ++i) #define REPIS(i, l, r, s) \ for (std::common_type_t \ i = (l), \ i##_last = (r); \ i < i##_last; i += (s)) #define REPR(i, n) for (auto i = (n); --i >= 0;) #define REPB(i, l, r) \ for (std::common_type_t i = (r), i##_last = (l); \ --i >= i##_last;) #define REPRS(i, l, r, s) \ for (std::common_type_t \ i = (l) + ((r) - (l)-1) / (s) * (s), \ i##_last = (l); \ i >= i##_last; (i -= (s))) #define REP(...) $OVERLOAD4(__VA_ARGS__, REPIS, REPF, REPI, LOOP)(__VA_ARGS__) #define REPD(...) $OVERLOAD4(__VA_ARGS__, REPRS, REPB, REPR)(__VA_ARGS__) #define FORO(i, n) \ for (int i = 0, i##_last = static_cast(n); i <= i##_last; ++i) #define FORI(i, l, r) \ for (std::common_type_t i = (l), i##_last = (r); \ i <= i##_last; ++i) #define FORIS(i, l, r, s) \ for (std::common_type_t \ i = (l), \ i##_last = (r); \ i <= i##_last; i += (s)) #define FORRO(i, n) for (auto i = (n); i >= 0; --i) #define FORR(i, l, r) \ for (std::common_type_t i = (r), i##_last = (l); \ i >= i##_last; --i) #define FORRS(i, l, r, s) \ for (std::common_type_t \ i = (l) + ((r) - (l)) / (s) * (s), \ i##_last = (l); \ i >= i##_last; i -= (s)) #define FOR(...) $OVERLOAD4(__VA_ARGS__, FORIS, FORI, FORO)(__VA_ARGS__) #define FORD(...) $OVERLOAD4(__VA_ARGS__, FORRS, FORR, FORRO)(__VA_ARGS__) #define ITR1(e0, v) for (const auto &e0 : (v)) #define ITRP1(e0, v) for (auto e0 : (v)) #define ITRR1(e0, v) for (auto &e0 : (v)) #define ITR2(e0, e1, v) for (const auto [e0, e1] : (v)) #define ITRP2(e0, e1, v) for (auto [e0, e1] : (v)) #define ITRR2(e0, e1, v) for (auto &[e0, e1] : (v)) #define ITR3(e0, e1, e2, v) for (const auto [e0, e1, e2] : (v)) #define ITRP3(e0, e1, e2, v) for (auto [e0, e1, e2] : (v)) #define ITRR3(e0, e1, e2, v) for (auto &[e0, e1, e2] : (v)) #define ITR4(e0, e1, e2, e3, v) for (const auto [e0, e1, e2, e3] : (v)) #define ITRP4(e0, e1, e2, e3, v) for (auto [e0, e1, e2, e3] : (v)) #define ITRR4(e0, e1, e2, e3, v) for (auto &[e0, e1, e2, e3] : (v)) #define ITR(...) $OVERLOAD5(__VA_ARGS__, ITR4, ITR3, ITR2, ITR1)(__VA_ARGS__) #define ITRP(...) \ $OVERLOAD5(__VA_ARGS__, ITRP4, ITRP3, ITRP2, ITRP1)(__VA_ARGS__) #define ITRR(...) \ $OVERLOAD5(__VA_ARGS__, ITRR4, ITRR3, ITRR2, ITRR1)(__VA_ARGS__) std::ostream &operator<<(std::ostream &dest, __int128_t value) { std::ostream::sentry s(dest); if (s) { __uint128_t tmp = value < 0 ? -value : value; char buffer[128]; char *d = std::end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while (tmp != 0); if (value < 0) { --d; *d = '-'; } int len = std::end(buffer) - d; if (dest.rdbuf()->sputn(d, len) != len) { dest.setstate(std::ios_base::badbit); } } return dest; } template class WeightedUnionFind { public: WeightedUnionFind() = default; /// @brief 重み付き Union-Find 木を構築します。 /// @param n 要素数 explicit WeightedUnionFind(size_t n) : m_parentsOrSize(n, -1), m_diffWeights(n) {} /// @brief 頂点 i の root のインデックスを返します。 /// @param i 調べる頂点のインデックス /// @return 頂点 i の root のインデックス int find(int i) { if (m_parentsOrSize[i] < 0) { return i; } const int root = find(m_parentsOrSize[i]); m_diffWeights[i] += m_diffWeights[m_parentsOrSize[i]]; // 経路圧縮 return (m_parentsOrSize[i] = root); } /// @brief a のグループと b のグループを統合します。 /// @param a 一方のインデックス /// @param b 他方のインデックス /// @param w (b の重み) - (a の重み) /// a を含むグループと b を含むグループを併合し、b の重みは a と比べて w /// 大きくなるようにする void merge(int a, int b, Type w) { w += weight(a); w -= weight(b); a = find(a); b = find(b); if (a != b) { // union by size (小さいほうが子になる) if (-m_parentsOrSize[a] < -m_parentsOrSize[b]) { std::swap(a, b); w = -w; } m_parentsOrSize[a] += m_parentsOrSize[b]; m_parentsOrSize[b] = a; m_diffWeights[b] = w; } } /// @brief (b の重み) - (a の重み) を返します。 /// @param a 一方のインデックス /// @param b 他方のインデックス /// @remark a と b が同じグループに属さない場合の結果は不定です。 /// @return (b の重み) - (a の重み) ///(b の重み) - (a の重み) を返す。a と b /// が同じグループに属さない場合の結果は不定 Type diff(int a, int b) { return (weight(b) - weight(a)); } /// @brief a と b が同じグループに属すかを返します。 /// @param a 一方のインデックス /// @param b 他方のインデックス /// @return a と b が同じグループに属す場合 true, それ以外の場合は false /// a と b が同じグループに属すかを返す bool connected(int a, int b) { return (find(a) == find(b)); } /// @brief i が属するグループの要素数を返します。 /// @param i インデックス /// @return i が属するグループの要素数 int size(int i) { return -m_parentsOrSize[find(i)]; } private: // m_parentsOrSize[i] は i の 親, // ただし root の場合は (-1 * そのグループに属する要素数) std::vector m_parentsOrSize; // 重み std::vector m_diffWeights; Type weight(int i) { find(i); // 経路圧縮 return m_diffWeights[i]; } }; __int128 parse(string &s) { __int128 ret = 0; for (int i = 0; i < s.length(); i++) if ('0' <= s[i] && s[i] <= '9') ret = 10 * ret + s[i] - '0'; return ret; } ll GCD(ll m, ll n) { // ベースケース if (n == 0) return m; // 再帰呼び出し return GCD(n, m % n); } ll minlong = 0; long long Power(long long a, long long b, long long m) { long long p = a, Answer = 1; for (int i = 0; i < 63; i++) { ll wari = (1LL << i); if ((b / wari) % 2 == 1) { Answer %= m; Answer = (Answer * p) % m; // 「a の 2^i 乗」が掛けられるとき } p %= m; p = (p * p) % m; } return Answer; } // a ÷ b を m で割った余りを返す関数 long long Division(long long a, long long b, long long m) { return (a * Power(b, m - 2, m)) % m; } // nCr mod 998244353 を返す関数 long long nCk(ll n, ll r) { const long long M = 998244353; // 手順 1: 分子 a を求める long long a = 1; for (int i = 1; i <= n; i++) a = (a * i) % M; // 手順 2: 分母 b を求める long long b = 1; for (int i = 1; i <= r; i++) b = (b * i) % M; for (int i = 1; i <= n - r; i++) b = (b * i) % M; // 手順 3: 答えを求める return Division(a, b, M); } using Interval = pair; // 終点時間でsortをかけるのに必要(区間スケジューリング問題など) bool cmp(const Interval &a, const Interval &b) { return a.second < b.second; } vll dycstra(vector>> G, ll N, ll K) { vb kaku(N, false); vll cur(N, INF); cur[K] = 0; priority_queue, vector>, greater>> Q; Q.push(make_pair(cur[K], K)); while (!Q.empty()) { ll pos = Q.top().second; Q.pop(); if (kaku[pos]) continue; kaku[pos] = true; for (ll i = 0; i < G[pos].size(); i++) { ll nex = G[pos][i].first; ll cost = G[pos][i].second; if (cur[nex] > cur[pos] + cost) { cur[nex] = cur[pos] + cost; Q.push(make_pair(cur[nex], nex)); } } } return cur; } template void Print(vector &A) { rep(i, A.size()) { cout << A[i] << ' '; } cout << endl; } template class BIT { public: BIT() = default; // 長さ size の数列で初期化 explicit BIT(size_t size) : m_bit(size + 1) {} // 数列で初期化 explicit BIT(const std::vector &v) : BIT(v.size()) { for (int i = 0; i < v.size(); ++i) { add((i + 1), v[i]); } } // 閉区間 [1, r] の合計を返す (1-based indexing) xy sum(int r) const { xy ret = 0; for (; 0 < r; r -= (r & -r)) { ret += m_bit[r]; } return ret; } // 閉区間 [l, r] の合計を返す (1-based indexing) xy sum(int l, int r) const { return (sum(r) - sum(l - 1)); } // 数列の i 番目の要素を加算 (1-based indexing) void add(int i, xy value) { for (; i < m_bit.size(); i += (i & -i)) { m_bit[i] += value; } } private: std::vector m_bit; }; // Binary Indexed Tree (1.2 区間加算対応) // 1-based indexing template class BIT_RAQ { public: BIT_RAQ() = default; explicit BIT_RAQ(size_t size) : m_bit0(size), m_bit1(size) {} explicit BIT_RAQ(const std::vector &v) : m_bit0(v), m_bit1(v.size()) {} // 閉区間 [1, r] の合計を返す (1-based indexing) x sum(int r) const { return (m_bit0.sum(r) + m_bit1.sum(r) * r); } // 閉区間 [l, r] の合計を返す (1-based indexing) x sum(int l, int r) const { return (sum(r) - sum(l - 1)); } // 数列の i 番目の要素を加算 (1-based indexing) void add(int i, x value) { m_bit0.add(i, value); } // 閉区間 [l, r] の要素を加算 (1-based indexing) void add(int l, int r, x value) { x a = (-value * (l - 1)), b = (value * r); m_bit0.add(l, a); m_bit0.add((r + 1), b); m_bit1.add(l, value); m_bit1.add((r + 1), -value); } private: BIT m_bit0; BIT m_bit1; }; vll BFS(vvll &G, ll &x) { vll cut(G.size(), INF); queue Q; Q.push(x); cut[x] = 0; while (!Q.empty()) { ll a = Q.front(); Q.pop(); rep(i, G[a].size()) { if (cut[G[a][i]] > cut[a] + 1) { cut[G[a][i]] = cut[a] + 1; Q.push(G[a][i]); } } } return cut; } void Yes(bool b) { if (b) cout << "Yes" << endl; else cout << "No" << endl; } vector yaku(long long n) { vector ret; for (long long i = 1; i * i <= n; i++) { if (n % i == 0) { ret.push_back(i); if (i * i != n) ret.push_back(n / i); } } sort(ret.begin(), ret.end()); // 昇順に並べる return ret; } priority_queue, vector>, greater>> Q; double randouble() { return 1.0 * rand() / RAND_MAX; } struct Mo { int n; vector> lr; explicit Mo(int n) : n(n) {} // nの値の設定を行う。 void add(int l, int r) { /* [l, r) */ lr.push_back({l, r}); } template void build(const AL &add_left, const AR &add_right, const EL &erase_left, const ER &erase_right, const O &out) { int q = (int)lr.size(); // lr.size()はクエリの数に等しい。 int bs = n / min(n, sqrt(q)); // 事実上bs>0となるように設定、 // cout << bs << endl; vector ord(q); iota(begin(ord), end(ord), 0); sort(begin(ord), end(ord), [&](int a, int b) { int ablock = lr[a].first / bs, bblock = lr[b].first / bs; if (ablock != bblock) return ablock < bblock; // return (ablock & 1) ? lr[a].second > lr[b].second : lr[a].second < lr[b].second; // 偶奇で昇順・降順を分けることによって計算量が定数倍高速化する。 }); int l = 0, r = 0; for (auto idx : ord) { // cout << idx << endl; while (l > lr[idx].first) add_left(--l); while (r < lr[idx].second) add_right(r++); while (l < lr[idx].first) erase_left(l++); while (r > lr[idx].second) erase_right(--r); out(idx); } } template void build(const A &add, const E &erase, const O &out) { build(add, add, erase, erase, out); } }; struct TRI { ll a; ll b; ll c; }; bool operator>(const TRI &r, const TRI &l) { return (r.a > l.a | (r.a == l.a & r.b > l.b) | (r.a == l.a & r.b == l.b & r.c > l.c)); } bool operator<(const TRI &r, const TRI &l) { return (r.a < l.a | (r.a == l.a & r.b < l.b) | (r.a == l.a & r.b == l.b & r.c < l.c)); } struct TR { ll a; ll b; ll c; ll d; }; bool operator>(const TR &r, const TR &l) { return (r.a > l.a | (r.a == l.a & r.b > l.b) | (r.a == l.a & r.b == l.b & r.c > l.c)); } bool operator<(const TR &r, const TR &l) { return (r.a < l.a | (r.a == l.a & r.b < l.b) | (r.a == l.a & r.b == l.b & r.c < l.c)); } struct TR5 { ll a; ll b; ll c; ll d; ll e; }; bool operator>(const TR5 &r, const TR5 &l) { return (r.a > l.a | (r.a == l.a & r.b > l.b) | (r.a == l.a & r.b == l.b & r.c > l.c)); } bool operator<(const TR5 &r, const TR5 &l) { return (r.a < l.a | (r.a == l.a & r.b < l.b) | (r.a == l.a & r.b == l.b & r.c < l.c)); } // Sはdataを表している。 using S = ll; // Fはlazy(遅延伝搬用)を表している using F = ll; // 区間取得をどのようにするかを定義する。RMQだったらmin(a,b)とかになる。 S op(S a, S b) { return a + b; }; // op(e,a)=op(a,e)=aとなるような単位元を定義する。RMQの場合はINFが安牌 S e() { return 0; } // 親のlazyが子のdataに対してどの様に作用させるかを定義する。区間加算をする場合はただ足せば良い S mapping(F f, S x) { return x + f; } /*親のlazyが子のlazyに対してどの様に作用させるかを定義する。区間加算をする場合はただ足せば良い ただ可変では無い場合fが後の操作である事を留意しておくと良い*/ F composition(F f, F g) { return f + g; } // mapping(a,id)=aとなる様なidを設定すれば良い今回の区間加算の場合は0が適する。区間乗算の場合は1が適する F id() { return 0; } ll half = 499122177; // 条件を満たす場合オイラーツアーを考えれば出来る。 // 重要なのは求める次数を満たす辺を構築すること // G:グラフ,P:オイラーツアーで探索した際に通った辺の番号の配列,in,out:最初と最後に通った時刻 // U[辺の番号]={親,現在いる位置}正の値だったら終点、それ以外親を出力することで頂点で表した経路の復元が可能 // num=辺の番号を記録,cou=時刻を記録 // 返り値: a と b の最大公約数 // ax + by = gcd(a, b) を満たす (x, y) が格納される long long extGCD(long long a, long long b, long long &x, long long &y) { if (b == 0) { x = 1; y = 0; return a; } long long d = extGCD(b, a % b, y, x); y -= a / b * x; return d; } vll toposo(vvll &G) { // 帰りがけでやりたい場合はstack、幅優先でやりたい場合はqueueで行う stack Q; ll n = G.size(); vll A(n, 0); rep(i, n) { rep(j, G[i].size()) { A[G[i][j]]++; } } vb han(n, false); rep(i, n) { if (A[i] == 0) { Q.push(i); han[i] = true; } } vll B; while (!Q.empty()) { ll a = Q.top(); Q.pop(); B.push_back(a); rep(i, G[a].size()) { if (!han[G[a][i]]) { A[G[a][i]]--; if (A[G[a][i]] == 0) { Q.push(G[a][i]); han[G[a][i]] = true; } } } } if (B.size() != n) { vll C(n, -2); return C; } return B; } #include // ax+bのようなグラフの最小値をクエリ一個あたりO(1)で算出することが出来る。 // 条件は2つ存在する。 // 1.追加される順に傾きは単調減少でなければならない(傾きに関してソートする必要性が生じる) // 2.追加される順にxは単調増加でなければならない(クエリ先読み等のひと手間が必要になる可能性がある) // 2つの条件が満たせない場合はこのサンプルを使うことが出来ない(クエリが2種類存在し、直線の追加とxを指定して最小値を求める動作を平行して行う場合等) struct ConvexHullTrick { std::deque> dq; // (傾き、切片) void add(long long a, long long b) { std::pair p0 = std::make_pair(a, b); while (dq.size() >= 2) { int sz = dq.size(); std::pair p1 = dq[sz - 1]; std::pair p2 = dq[sz - 2]; if ((p0.second - p1.second) * (p0.first - p2.first) < (p0.second - p2.second) * (p0.first - p1.first)) break; // 交点のx座標を比較 dq.pop_back(); } dq.push_back(p0); } long long query(long long x) { while (dq.size() >= 2) { long long v1 = dq[0].first * x + dq[0].second; long long v2 = dq[1].first * x + dq[1].second; if (v1 <= v2) break; dq.pop_front(); } return dq[0].first * x + dq[0].second; } }; // if(a <= b + EPS) // a <= b // if(a < b - EPS) // a < b // if(abs(a - b) < EPS) // a == b // 頂点 s から頂点 t までの最大フローの総流量を返す struct Edge { long long to, cap, rev; }; class MaximumFlow { public: int size_ = 0; int level[2000]; int iter[2000]; vector G[2000]; // 頂点数 N の残余グラフを準備 void init(int N) { size_ = N; memset(G, {}, size_); for (int i = 0; i <= size_; i++) G[i].clear(); memset(level, -1,N); memset(iter, 0, N); } // 頂点 a から b に向かう、上限 c リットル/秒の辺を追加 void add_edge(int a, int b, long long c) { int Current_Ga = G[a].size(); // 現時点での G[a] の要素数 int Current_Gb = G[b].size(); // 現時点での G[b] の要素数 G[a].push_back(Edge{b, c, Current_Gb}); G[b].push_back(Edge{a, 0, Current_Ga}); } // 頂点 a から b に向かう、上限 c リットル/秒の辺と頂点 b から a // に向かう、上限 c リットル/秒の辺を追加 void Uadd_edge(int a, int b, long long c) { int Current_Ga = G[a].size(); // 現時点での G[a] の要素数 int Current_Gb = G[b].size(); // 現時点での G[b] の要素数 G[a].push_back(Edge{b, c, Current_Gb}); G[b].push_back(Edge{a, c, Current_Ga}); } // sからの最短距離をBDSで計算する void bfs(int s, int t) { memset(level, -1, sizeof(level)); queue que; level[s] = 0; que.push(s); while (!que.empty()) { int v = que.front(); que.pop(); for (int i = 0; i < G[v].size(); i++) { Edge &e = G[v][i]; if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; if (e.to == t) goto H; que.push(e.to); } } } H:; } // 深さ優先探索(F はスタートから pos に到達する過程での " // 残余グラフの辺の容量 " の最小値) 返り値は流したフローの量(流せない場合は // 0 を返す) long long dfs(int pos, int goal, long long F) { // ゴールに到着:フローを流せる! if (pos == goal) return F; // 探索する for (int &i = iter[pos]; i < G[pos].size(); i++) { Edge &e = G[pos][i]; if (e.cap > 0 && level[pos] < level[e.to]) { long long d = dfs(e.to, goal, min(F, e.cap)); // フローを流せる場合、残余グラフの容量を flow だけ増減させる if (d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } // すべての辺を探索しても見つからなかった ・・・ return 0; } // 頂点 s から頂点 t までの最大フローの総流量を返す long long max_flow(int s, int t) { long long Total_Flow = 0; while (true) { bfs(s, t); if (level[t] < 0) return Total_Flow; memset(iter, 0, sizeof(iter)); long long f = 0; while ((f = dfs(s, t, (long long)1e18)) > 0) Total_Flow += f; } } }; int main() { cout << fixed << setprecision(20); ll N, M; ll a = 0, b = 0; ll c = 0; ll p = 1; string S, T; ll H, W; ll K; ll t; cin >> N >> M >> K; vll A(M), B(M), C(M), D(M), E(M); rep(i, M) cin >> A[i] >> B[i] >> C[i] >> D[i] >> E[i]; MaximumFlow Z; Z.init(M + 2); rep(i, M) { if (A[i] == 1) Z.add_edge(0, i + 1, INF); if (B[i] == N) Z.add_edge(i + 1, M + 1, E[i]); } vector> G(N); rep(i, M) { G[A[i] - 1].push_back({C[i], D[i], B[i] - 1, E[i], i}); } rep(i, N) sort(ALL(G[i])); rep(i, N-1) { rep(j, G[i].size() - 1) { Z.add_edge(G[i][j].e + 1, G[i][j + 1].e + 1, INF); } rep(j, G[i].size()) { ll a = G[i][j].c; if (a != N) { rep(k, G[a].size()) { if (G[i][j].b + K <= G[a][k].a) { Z.add_edge(G[i][j].e + 1, G[a][k].e + 1, G[i][j].d); break; } } } } } cout << Z.max_flow(0, M + 1) << endl; }