#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=410000;
const ll INF=1e18; 
typedef vector<int> ve;
int n,m,w,mxn;
ve P;
struct edge{
	int x,y,a,b,c;
};
int val[N];
vector <edge> e;
vector <pair<int,pair<int,bool>>> ev; 
vector <int> ds[N];
struct str{
	int nw,lc[N<<6],rc[N<<6];
	ll a[N<<6];
	void p(int x,int y,int z,int k1,int k2,int l=1,int r=mxn){
		a[k1]=a[k2],lc[k1]=lc[k2],rc[k1]=rc[k2];
		if(x>y)
			return ;
		if(x<=l&&r<=y){
			a[k1]+=z;
			return ;
		}
		int mid=(l+r)>>1;
		if(x<=mid)
			p(x,y,z,lc[k1]=++nw,lc[k2],l,mid);
		if(mid+1<=y)
			p(x,y,z,rc[k1]=++nw,rc[k2],mid+1,r);
	}
	ll q(int x,int k,int l=1,int r=mxn){
		if(k==0)
			return 0;
		if(l==r)
			return a[k];
		int mid=(l+r)>>1;
		if(x<=mid)
			return a[k]+q(x,lc[k],l,mid);
		else
			return a[k]+q(x,rc[k],mid+1,r);
	}
}dog;
ve d[N];
int cnt[N];
int root[N];
struct node{
	int x,l,r;
};
deque <node> st[N];
ll f[N];
ll cst(int x,int y){
	if(e[x].b<=e[y].a)
		return f[x]+val[e[x].y]*dog.q(e[x].b,root[e[y].a]);
	return INF;
}
bool cmp(int x,int i,int j){
	return cst(i,x)>cst(j,x);
}
ll ans=INF;
ll solve(int nn,int mm,int ww,ve T,ve X,ve Y,ve A,ve B,ve C,ve L,ve R){
	n=nn,m=mm,w=ww;
	P.push_back(0);
	P.push_back(2e9);
	for(int i=0;i<n;i++)
		val[i]=T[i];
	for(int i=0;i<m;i++){
		P.push_back(A[i]);
		P.push_back(B[i]);
	}
	sort(P.begin(),P.end());
	unique(P.begin(),P.end());
	mxn=P.size();
	for(int i=0;i<m;i++){
		A[i]=lower_bound(P.begin(),P.end(),A[i])-P.begin()+1;
		B[i]=lower_bound(P.begin(),P.end(),B[i])-P.begin()+1;
	}
	for(int i=0;i<w;i++){
		L[i]=lower_bound(P.begin(),P.end(),L[i])-P.begin();
		R[i]=upper_bound(P.begin(),P.end(),R[i])-P.begin()+1;
		ds[R[i]].push_back(L[i]);
	}
	for(int i=1;i<=mxn;i++){
		dog.p(1,mxn,0,root[i]=++dog.nw,root[i-1]);
		for(int j=0;j<(int)ds[i].size();j++){
			int h=root[i];
			dog.p(1,ds[i][j],1,root[i]=++dog.nw,h);
		}
	}
	for(int i=0;i<m;i++)
		e.push_back({X[i],Y[i],A[i],B[i],C[i]});
	sort(e.begin(),e.end(),[](const edge x,const edge y){
		return x.a<y.a;
	});
	for(int i=0;i<m;i++){
		ev.push_back(make_pair(e[i].a,make_pair(i,0)));
		ev.push_back(make_pair(e[i].b,make_pair(i,1)));
	}
	for(int i=0;i<m;i++)
		d[e[i].x].push_back(i);
	sort(ev.begin(),ev.end(),[](const pair<int,pair<int,bool>> x,const pair<int,pair<int,bool>> y){
		return x.first==y.first?x.second.second>y.second.second:x.first<y.first;
	});
	for(int i=0;i<m;i++)
		f[i]=e[i].x==0?val[0]*dog.q(1,root[e[i].a]):INF;
	for(int x=0;x<2*m;x++){
		int i=ev[x].second.first,op=ev[x].second.second;
		if(op==0){
			cnt[e[i].x]++;
			if(st[e[i].x].empty()==0){
				f[i]=min(f[i],cst(st[e[i].x].front().x,i));
				st[e[i].x].front().l++;
				if(st[e[i].x].front().l>st[e[i].x].front().r)
					st[e[i].x].pop_front();
			}
			f[i]+=e[i].c;
			if(e[i].y==n-1)
				ans=min(ans,f[i]+val[n-1]*dog.q(e[i].b,root[mxn]));
		}
		else{
			if(cnt[e[i].y]==(int)d[e[i].y].size())
				continue;
			while(st[e[i].y].empty()==0&&cmp(d[e[i].y][st[e[i].y].back().l],st[e[i].y].back().x,i))
				st[e[i].y].pop_back();
			if(st[e[i].y].empty())
				st[e[i].y].push_back({i,cnt[e[i].y],(int)d[e[i].y].size()-1});
			else{
				int l=st[e[i].y].back().l,r=st[e[i].y].back().r;
				while(l!=r){
					int mid=(l+r)>>1;
					if(cmp(d[e[i].y][mid+1],st[e[i].y].back().x,i)==0)
						l=mid+1;
					else
						r=mid;
				}
				st[e[i].y].back().r=l;
				if(l+1<(int)d[e[i].y].size())
					st[e[i].y].push_back({i,l+1,(int)d[e[i].y].size()-1});
			}
		}
	}
	return ans==INF?-1:ans;
}