#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <string>
#include <queue>

using namespace std;

template<typename T>
class MaxFlow {
private:
  struct Edge {
    int v;
    int r;
    T c;
  };

private:
  std::vector<std::vector<Edge>> g;
  std::vector<int> d, it;

public:
  MaxFlow(int n) : g(n), d(n), it(n) {}

  void add(int u, int v, T c) {
    const int i = g[u].size();
    const int j = g[v].size();
    g[u].push_back({ v, j, c });
    g[v].push_back({ u, i, 0 });
  }

  T calc(int s, int t) {
    T sum = 0;
    while (bfs(s, t)) {
      T f;
      while ((f = dfs(s, t, std::numeric_limits<T>::max())) > 0) sum += f;
    }
    return sum;
  }

private:
  bool bfs(int s, int t) {
    std::fill(it.begin(), it.end(), 0);
    std::fill(d.begin(), d.end(), -1);
    d[s] = 0;
    std::queue<int> q;
    q.push(s);
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      for (Edge e : g[v]) {
        if (e.c > 0 && d[e.v] == -1) {
          d[e.v] = d[v] + 1;
          q.push(e.v);
        }
      }
    }
    return d[t] >= 0;
  }

  T dfs(int v, int t, T f) {
    if (v == t) return f;
    while (it[v] < g[v].size()) {
      Edge &e = g[v][it[v]++];
      if (e.c > 0 && d[v] < d[e.v]) {
        T ff = dfs(e.v, t, std::min(f, e.c));
        if (ff > 0) {
          e.c -= ff;
          g[e.v][e.r].c += ff;
          return ff;
        }
      }
    }
    return 0;
  }
};

int main() {
  int n, m, d;
  cin >> n >> m >> d;

  MaxFlow<long long> mf(m * 2 + 2);
  int src = m * 2;
  int sink = m * 2 + 1;

  vector<int> u(m), v(m), p(m), q(m), w(m);
  for (int i = 0; i < m; i++) {
    cin >> u[i] >> v[i] >> p[i] >> q[i] >> w[i];
    u[i]--;
    v[i]--;
  }
  for (int i = 0; i < m; i++) {
    if (u[i] == 0) {
      mf.add(src, i, 1e15);
    }
    if (v[i] == n - 1) {
      mf.add(i + m, sink, 1e15);
    }
    mf.add(i, i + m, w[i]);
    for (int j = 0; j < m; j++) if (i != j) {
      if (v[i] == u[j] && q[i] + d <= p[j]) {
        mf.add(i + m, j, 1e15);
      }
    }
  }
  cout << mf.calc(src, sink) << endl;
}