#include using namespace std; typedef long long ll; const int N = 10010, M = 4000010; const ll INF = 1e18; int n, m, k, S, T; struct Edge { ll u, v, p, q, w; }edges[N]; int h[N], e[M], ne[M], idx; ll d[N], cur[N], q[N], f[M]; void add(int a, int b, ll c) { e[idx] = b, ne[idx] = h[a], f[idx] = c, h[a] = idx ++ ; e[idx] = a, ne[idx] = h[b], h[b] = idx ++ ; } bool bfs() { int hh = 0, tt = 0; memset(d, -1, sizeof d); q[0] = S, d[S] = 0, cur[S] = h[S]; while (hh <= tt) { int t = q[hh ++ ]; for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] == -1 && f[i]) { d[j] = d[t] + 1; cur[j] = h[j]; if (j == T) return true; q[ ++ tt] = j; } } } return false; } ll find(int u, ll limit) { if (u == T) return limit; ll flow = 0; for (int i = h[u]; ~i; i = ne[i]) { cur[u] = i; int j = e[i]; if (d[j] == d[u] + 1 && f[i]) { ll t = find(j, min(f[i], limit - flow)); if (!t) d[j] = -1; f[i] -= t, f[i ^ 1] += t, flow += t; } } return flow; } ll dinic() { ll r = 0, flow = 0; while (bfs()) while (flow = find(S, INF)) r += flow; return r; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); memset(h, -1, sizeof h); cin >> n >> m >> k; for (int i = 1; i <= m; i ++ ) cin >> edges[i].u >> edges[i].v >> edges[i].p >> edges[i].q >> edges[i].w; for (int i = 1; i <= m; i ++ ) add(i, i + m, edges[i].w); for (int i = 1; i <= m; i ++ ) for (int j = 1; j <= m; j ++ ) if (i != j) { if (edges[i].v != edges[j].u) continue; if (edges[i].q + k > edges[j].p) continue; add(i + m, j, INF); } S = 0, T = m * 2 + 1; for (int i = 1; i <= m; i ++ ) { if (edges[i].u == 1) add(S, i, edges[i].w); if (edges[i].v == n) add(i + m, T, edges[i].w); } cout << dinic() << "\n"; return 0; }