#include<bits/stdc++.h> 
using namespace std;

#define ll long long
#define foru(a,b,c) for(ll a=b;a<=c;a++)

ll c,n,m,s,a[1005],f[20005],tot=0;
ll du[40005],dv[40005],ex[40005],ey[40005];
bool used[40005],inq[1005];
vector<vector<ll> >g(1005);
queue<ll>q;

void add(ll u,ll v,ll x,ll y){
    tot++;
    du[tot]=u;
    dv[tot]=v;
    ex[tot]=x;
    ey[tot]=y;
    used[tot]=0;
    g[u].push_back(tot);
}

int main(){
    freopen("recall.in","r",stdin);
    freopen("recall.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>c>>n>>m>>s;
    foru(i,1,n){
        cin>>a[i];
        g[i].clear();
        inq[i]=0;
    }
    ll u,v,x,y;
    foru(i,1,m){
        cin>>u>>v>>x>>y;
        add(u,v,x,y);
    }
    foru(i,1,n)f[i]=-4e18;
    f[1]=s+a[1];
    q.push(1);
    inq[1]=1;
    while(!q.empty()){
        ll u=q.front();
        q.pop();
        inq[u]=0;
        if(f[u]<0)continue;
        ll sz=g[u].size()-1;
        foru(i,0,sz){
            ll id=g[u][i];
            ll v=dv[id];
            if(f[v]<f[u]+a[v]){
                f[v]=f[u]+a[v];
                if(!inq[v]){
                    q.push(v);
                    inq[v]=1;
                }
            }
            if(!used[id]&&ex[id]>=1&&ex[id]<=n&&ey[id]>=1&&ey[id]<=n){
                used[id]=1;
                add(ex[id],ey[id],0,0);
            }
        }
    }
    if(f[n]<0)cout<<-1;
    else cout<<f[n];
    return 0;
}//20 10007 20 0