#include <bits/stdc++.h>
using namespace std;
#include <iostream>
#include <vector>
using ll = long long;
using ld = long double;
using Graph = vector<vector<int>>;
using vi = vector<int>;
using vl = vector<long>;
using vll = vector<long long>;
using vb = vector<bool>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vd = vector<double>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
using vc = vector<char>;
using vvc = vector<vc>;
using lll = __int128_t;
using vs = vector<string>;
using pii = pair<long long, long long>;
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 <class T>
inline T CHMAX(T &a, const T b) {
  return a = (a < b) ? b : a;
}
template <class T>
inline T CHMIN(T &a, const T b) {
  return a = (a > b) ? b : a;
}
#include <algorithm>  // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <bitset>     // bitset
#include <cctype>     // isupper, islower, isdigit, toupper, tolower
#include <cstdint>    // int64_t, int*_t
#include <cstdio>     // printf
#include <deque>      // deque
#include <iostream>   // cout, endl, cin
#include <map>        // map
#include <queue>      // queue, priority_queue
#include <set>        // set
#include <stack>      // stack
#include <string>     // string, to_string, stoi
#include <tuple>      // tuple, make_tuple
#include <unordered_map>  // unordered_map
#include <unordered_set>  // unordered_set
#include <utility>        // pair, make_pair
#include <vector>         // vector
using namespace std;

#include <type_traits>

#define LOOP(n) REPI($_, (n))

#define REPI(i, n) \
  for (int i = 0, i##_length = static_cast<int>(n); i < i##_length; ++i)
#define REPF(i, l, r)                                                        \
  for (std::common_type_t<decltype(l), decltype(r)> i = (l), i##_last = (r); \
       i < i##_last; ++i)
#define REPIS(i, l, r, s)                                        \
  for (std::common_type_t<decltype(l), decltype(r), decltype(s)> \
           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<decltype(l), decltype(r)> i = (r), i##_last = (l); \
       --i >= i##_last;)
#define REPRS(i, l, r, s)                                        \
  for (std::common_type_t<decltype(l), decltype(r), decltype(s)> \
           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<int>(n); i <= i##_last; ++i)
#define FORI(i, l, r)                                                        \
  for (std::common_type_t<decltype(l), decltype(r)> i = (l), i##_last = (r); \
       i <= i##_last; ++i)
#define FORIS(i, l, r, s)                                        \
  for (std::common_type_t<decltype(l), decltype(r), decltype(s)> \
           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<decltype(l), decltype(r)> i = (r), i##_last = (l); \
       i >= i##_last; --i)
#define FORRS(i, l, r, s)                                        \
  for (std::common_type_t<decltype(l), decltype(r), decltype(s)> \
           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 Type>
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<int> m_parentsOrSize;

  // 重み
  std::vector<Type> 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<ll, ll>;
// 終点時間でsortをかけるのに必要(区間スケジューリング問題など)
bool cmp(const Interval &a, const Interval &b) { return a.second < b.second; }
vll dycstra(vector<vector<pair<ll, ll>>> G, ll N, ll K) {
  vb kaku(N, false);
  vll cur(N, INF);
  cur[K] = 0;
  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> 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 <typename T>
void Print(vector<T> &A) {
  rep(i, A.size()) { cout << A[i] << ' '; }
  cout << endl;
}
template <typename xy>
class BIT {
 public:
  BIT() = default;

  // 長さ size の数列で初期化
  explicit BIT(size_t size) : m_bit(size + 1) {}

  // 数列で初期化
  explicit BIT(const std::vector<xy> &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<xy> m_bit;
};

// Binary Indexed Tree (1.2 区間加算対応)
// 1-based indexing
template <typename x>
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<x> &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<x> m_bit0;

  BIT<x> m_bit1;
};
vll BFS(vvll &G, ll &x) {
  vll cut(G.size(), INF);
  queue<ll> 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<long long> yaku(long long n) {
  vector<long long> 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<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> Q;

double randouble() { return 1.0 * rand() / RAND_MAX; }
struct Mo {
  int n;
  vector<pair<int, int>> lr;

  explicit Mo(int n) : n(n) {}  // nの値の設定を行う。

  void add(int l, int r) { /* [l, r) */
    lr.push_back({l, r});
  }

  template <typename AL, typename AR, typename EL, typename ER, typename O>
  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<int>(n, sqrt(q));  // 事実上bs>0となるように設定、
    // cout << bs << endl;
    vector<int> 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 <typename A, typename E, typename O>
  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<ll> 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 <bits/stdc++.h>
// ax+bのようなグラフの最小値をクエリ一個あたりO(1)で算出することが出来る。
// 条件は２つ存在する。
// 1.追加される順に傾きは単調減少でなければならない(傾きに関してソートする必要性が生じる)
// 2.追加される順にxは単調増加でなければならない(クエリ先読み等のひと手間が必要になる可能性がある)
// ２つの条件が満たせない場合はこのサンプルを使うことが出来ない(クエリが２種類存在し、直線の追加とxを指定して最小値を求める動作を平行して行う場合等)

struct ConvexHullTrick {
  std::deque<std::pair<long long, long long>> dq;  // （傾き、切片）

  void add(long long a, long long b) {
    std::pair<long long, long long> p0 = std::make_pair(a, b);
    while (dq.size() >= 2) {
      int sz = dq.size();
      std::pair<long long, long long> p1 = dq[sz - 1];
      std::pair<long long, long long> 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<Edge> 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<int> 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<vector<TR5>> 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;
}