#include<bits/stdc++.h>
using namespace std;
#define arep(i,x,n) for(int i=int(x);i<(int)(n);i++)
#define rep(i,n) for(long long i = 0;i < n;++i)
#define pi 3.141592653589793
#define eps 0.00000001
#define INF 1e9+7  
using ll = long long; 
using P=pair<int,int>;
using lP=pair<ll,ll>;
using fP=pair<double,double>;
ll const mod=998244353;
const ll MAX=1010;
using vi=vector<int>;
using vc=vector<char>;
using vs=vector<string>;
using vvi =vector<vector<int>>;
using vvc=vector<vector<char>>;
using vvp =vector<vector<P>>;
int d;
struct edge{
    int to,cap,rev,st,et;
    edge(int t,int c,int r,int s,int e)
    : to(t),cap(c),rev(r),st(s),et(e){}
};

struct graf{
    vector<edge> G[MAX];
    int used[MAX];

    void init(){memset(used,0,sizeof(used));}
    void add(int from,int to,int cap,int st,int et){
        G[from].push_back(edge(to,cap,(int)G[to].size(),st,et));
        G[to].push_back(edge(from,0,(int)G[from].size()-1,INF,st));
    }

    int dfs(int s, int t, int f, int time){
        if(s==t)return f;
        used[s]=1;
        for(edge& e:G[s]){
            if(used[e.to]==1||e.cap<=0||time>0&&time+d>e.st)continue;
            int x=dfs(e.to,t,min(f,e.cap),e.et);
            if(x<=0)continue;
            e.cap-=x;
            G[e.to][e.rev].cap+=x;
            return x;
        }
        return 0;
    }

    int max_flow(int s,int t){
        int ans=0;
        while(1){
            init();
            int f=dfs(s,t,INF,0);
            if(f==0)return ans;
            ans+=f;
        }
    }
    
};

int main(){
    int n,m;
    cin>>n>>m>>d;
    graf mf;
    rep(i,m){
        int u,v,p,q,w;
        cin>>u>>v>>p>>q>>w;
        u--,v--;
        mf.add(u,v,w,p,q);
    }
    cout<<mf.max_flow(0,n-1)<<endl;
    return 0;
}