#include <iostream>
#include <vector>
#include <cstdio>
#include <utility>
#include <queue>
#include <cstring>
using namespace std;
int c,n,m,s,num=0;
int ans=-1;
int a[1003];
int x[20004],y[20004];
vector<pair<int,int>>ve[1003];
bool vi[1003],vis[20004];
void dfs(int u,int vl) {
	if(u==n) {
		ans=max(ans,vl);
		return;
	}
	for(auto i:ve[u]) {
		int v=i.first,id=i.second;
		if(vis[id]) continue;
		vis[id]=1;
		if(a[v]+vl>=0) {
			if(x[id]!=0) {
				ve[x[id]].push_back(make_pair(y[id],++num));
			}
			if(vi[v]) {
				vi[v]=1;
				dfs(v,a[v]+vl);
				vi[v]=0;
			} else {
				dfs(v,vl);
			}
			if(x[id]!=0) {
				num--;
				ve[x[id]].pop_back();
			}
		}
		vis[id]=0;
	}
}
int dis[1003];
int tot[1003];
int main() {
    freopen("recall.in","r",stdin);
    freopen("recall.out","w",stdout);
    cout<<-1;
    return 0;
	cin>>c>>n>>m>>s;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
	}
	for(int i=1; i<=m; i++) {
		int u,v,xx,yy;
		cin>>u>>v>>xx>>yy;
		num++;
		x[num]=xx;
		y[num]=yy;
		ve[u].push_back(make_pair(v,num));
	}
	if(c==1) {
		if(s+a[1]<0) {
			cout<<-1;
			return 0;
		}
		dfs(1,s+a[1]);
		cout<<ans;
		return 0;
	}
	if(c==3) {
		memset(dis,0xc0,sizeof(dis));
		if(s+a[1]<0) {
			cout<<-1;
			return 0;
		}
		dis[1]=s+a[1];
		queue<int>q;
		q.push(1);
		while(!q.empty()) {
			int u=q.front();
			q.pop();
			for(auto i:ve[u]) {
				int v=i.first;
				if(dis[v]<dis[u]+a[v]&&dis[u]+a[v]>=0) {
					dis[v]=dis[u]+a[v];
					q.push(v);
					tot[v]++;
					if(tot[v]>n+10) {
						cout<<-1;
						return 0;
					}
				}
			}
		}
		cout<<max(dis[n],-1);
		return 0;
	}
	cout<<-1;
	return 0;
}