#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define mkp(a, b) make_pair(a, b)
#define pb(t) push_back(t)
#define ft first
#define sc second
#define pt(num) cout << num << "\n"
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
#define max(a, b) ((a)>(b) ? (a):(b))
#define min(a, b) ((a)<(b) ? (a):(b))
#define chmax(a, b) (a<b ? a=b : 0)
#define chmin(a, b) (a>b ? a=b : 0)
#define INF 1000000000000000000
#define MOD 1000000007LL
#define MAX 101010
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef map<ll, ll> Map;

class Edge {
public:
    ll t, cap, rev, dep, arr;
    Edge(ll t, ll cap, ll rev, ll dep, ll arr):
    t(t), cap(cap), rev(rev), dep(dep), arr(arr) {}
};

ll N;
vector<Edge> g[111];
ll used[111];

ll dfs(ll v, ll goal, ll f, ll time) {
    if(v==goal) return f;
    used[v]=1;
    ll i;
    for(i=0; i<g[v].size(); i++) {
        Edge &e=g[v][i];
        if(time>e.dep) continue;
        if(!used[e.t] && e.cap>0) {
            ll d=dfs(e.t, goal, min(f, e.cap), time+e.arr);
            if(d>0) {
                e.cap-=d;
                g[e.t][e.rev].cap+=d;
                return d;
            }
        }
    }
    
    return 0;   //goalまでのパスが見つからなかったとき
}

ll maxFlow(ll s, ll t) {
    ll flow=0;
    while(1) {
        memset(used, 0, sizeof(used));
        
        ll f=dfs(s, t, INF, 0);
        if(f==0) return flow;
        flow+=f;
    }
}

void addEdge(ll from, ll to, ll dep, ll arr, ll cap) {
    g[from].pb(Edge(to, cap, g[to].size(), dep, arr));
    g[to].pb(Edge(from, 0, g[from].size()-1, dep, arr));
}

int main(void) {
    ll M, d;
    cin >> N >> M >> d;
    ll i;
    
    for(i=0; i<M; i++) {
        ll u, v, p, q, w;
        cin >> u >> v >> p >> q >> w;
        u--; v--;
        addEdge(u, v, p, q+d, w);
    }
    
    pt(maxFlow(0, N-1));
    
}