#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+15;
const double EPS=1e-9;
const int MOD=1000000007;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

struct edge{int to,cap,rev; };

vector<edge> G[20000];
int level[20000],iter[20000];

void add_edge(int from,int to,int cap){
	G[from].push_back((edge){to,cap,G[to].size()});
	G[to].push_back((edge){from,0,G[from].size() - 1});
}

void bfs(int s){
	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;
				que.push(e.to);
			}
		}
	}
}

int dfs(int v,int t,int f){
	if(v == t) return f;
	for(int &i = iter[v];i < G[v].size();i++){
		edge &e = G[v][i];
		if(e.cap > 0 && level[v] < level[e.to]){
			int d = dfs(e.to,t,min(f,e.cap));
			if(d > 0){
				e.cap -= d;
				G[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}

int max_flow(int s,int t){
	int flow = 0;
	while(1){
		bfs(s);
		if(level[t] < 0) return flow;
		memset(iter,0,sizeof(iter));
		int f;
		while((f = dfs(s,t,INF)) > 0) flow += f;
	}
}

signed main(){
	int n,m,d,ans = 0,u[1000],v[1000],p[1000],q[1000],w[1000],cnt = 0;
	vector<int> tim[1000],ind[1000];
	cin >> n >> m >> d;
	for(int i = 0;i < m;i++){
		cin >> u[i] >> v[i] >> p[i] >> q[i] >> w[i]; u[i]--;v[i]--;q[i] += d;
		tim[u[i]].pb(p[i]);
		tim[v[i]].pb(q[i]);
	}
	for(int i = 0;i < n;i++){
		sort(all(tim[i]));
		tim[i].erase(unique(all(tim[i])),tim[i].end());
		for(int j = 0;j < tim[i].size();j++){
			if(j) add_edge(cnt - 1,cnt,INF);
			ind[i].pb(cnt++);
		}
	}
	for(int i = 0;i < m;i++){
		int ind1 = lower_bound(all(tim[u[i]]),p[i]) - tim[u[i]].begin();
		int ind2 = lower_bound(all(tim[v[i]]),q[i]) - tim[v[i]].begin();
		add_edge(ind[u[i]][ind1],ind[v[i]][ind2],w[i]);
	}
	if(ind[0].size() && ind[n - 1].size()) ans = max_flow(ind[0][0],ind[n - 1].back());
	cout << ans << endl;
	return 0;
}