#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005,C=1000005;
int n,m,d,u[N],v[N],p[N],q[N],w[N],s,t,cnt,ans,head[C],dep[C],cur[C];
struct edge
{
	int to,nxt,w,f;
}e[C];
void add(int u,int v,int w)
{
	e[cnt]={v,head[u],w,0};
	head[u]=cnt++;
}
void addrel(int u,int v,int w)
{
	add(u,v,w);
	add(v,u,0);
}
int bfs()
{
	queue<int> q;
	memset(dep,0,sizeof(dep));
	dep[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u],v,w,f;~i;i=e[i].nxt)
		{
			v=e[i].to;w=e[i].w;f=e[i].f;
			if(dep[v]||w<=f)continue;
			dep[v]=dep[u]+1;
			q.push(v);
		}
	}
	return dep[t];
}
int dfs(int u,int rm)
{
	if(u==t||!rm)return rm;
	int res=0;
	for(int &i=cur[u],v,w,f,fl;~i;i=e[i].nxt)
	{
		v=e[i].to;w=e[i].w,f=e[i].f;
		if(dep[v]!=dep[u]+1)continue;
		fl=dfs(v,min(rm-res,w-f));
		if(!fl)continue;
		res+=fl;
		e[i].f+=fl;
		e[i^1].f-=fl;
		if(res==rm)return rm;
	}
	return res;
}
int dinic()
{
	int res=0;
	while(bfs())
	{
		memcpy(cur,head,sizeof(cur));
		res+=dfs(s,0x3f3f3f3f);
	}
	return res;
}
signed main()
{
	memset(head,-1,sizeof(head));
	cin>>n>>m>>d;t=2*m+1;
	for(int i=1;i<=m;i++)
	{
		cin>>u[i]>>v[i]>>p[i]>>q[i]>>w[i];
		if(u[i]==1)addrel(s,i,0x3f3f3f3f);
		if(v[i]==n)addrel(i+m,t,0x3f3f3f3f);
		addrel(i,i+m,w[i]);
	}
	for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)if(u[j]==v[i]&&p[j]>=q[i]+d)addrel(i+m,j,0x3f3f3f3f);
	cout<<dinic();
}