#include<bits/stdc++.h>
using namespace std;
struct E {int v,x,y;};
vector<E> e[1005];
int a[1005],n,m,s,c;
bool v[1005],b[1005];
priority_queue<pair<int,int> > qn;
vector<int> qp;
void ad(int,int,int,int);
void act(int V,int x,int y) {
	if(!b[V]) {
		b[V]=1;
		if(a[V]>=0)qp.push_back(V);
		else qn.push({a[V],V});
	}
	if(x)ad(x,y,0,0);
}
void ad(int u,int V,int x,int y){
	e[u].push_back({V,x,y});
	if(v[u])act(V,x,y);
}
void go(int u) {
	int sz=e[u].size();
	for(int i=0;i<sz;i++)act(e[u][i].v,e[u][i].x,e[u][i].y);
}
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;
	for(int i=1; i<=n;++i)cin>>a[i];
	for(int i=0,u,V,x,y;i<m;++i) {
		cin>>u>>V>>x>>y;
		ad(u,V,x,y);
	}
	v[1]=1;
	s+=a[1];
	b[1]=1;
	if(s<0){
		cout<<-1;
		return 0;
	}
	go(1);
	while(1){
		while(!qp.empty()) {
			int u=qp.back();
			qp.pop_back();
			if(v[u])continue;
			v[u]=1;
			s+=a[u];
			go(u);
		}
		if(v[n]) {
			cout<<s;
			return 0;
		}
		if(qn.empty()) {
			cout<<-1;
			return 0;
		}
		pair<int,int> t=qn.top();
		qn.pop();
		int u=t.second;
		if(v[u])continue;
		if(s+a[u]<0) {
			cout<<-1;
			return 0;
		}
		v[u]=1;
		s+=a[u];
		go(u);
	}
}