#include<bits/stdc++.h>
using namespace std;
const int N=200005,M=N<<5,inf=1e9+7;
const long long INF=1e18;
int n,m,k;
int a[N];
struct E{int x,y,a,b,w,id;}e[N],e1[N],e2[N];
bool cmp1(E x,E y){return x.a<y.a;}
bool cmp2(E x,E y){return x.b<y.b;}
long long dis[N];
struct nd
{
	int l,r;
	bool operator <(const nd &b) const
	{
		return l<b.l;
	}
}b[N];
int h[N],cnth;
int rt[N],idx;
int L[M],R[M],ls[M],rs[M];
int sum[M];
void pushup(int x)
{
	sum[x]=0;
	if(ls[x]) sum[x]+=sum[ls[x]];
	if(rs[x]) sum[x]+=sum[rs[x]];
}
int build(int l,int r,int x)
{
	L[x]=l,R[x]=r;
	if(l==r) return x;
	int mid=(l+r)/2;
	ls[x]=build(l,mid,++idx);
	rs[x]=build(mid+1,r,++idx);
	pushup(x);
	return x;
}
void update(int id,int x,int k,int ver)
{
	idx++;
	L[idx]=L[x],R[idx]=R[x];
	ls[idx]=ls[x],rs[idx]=rs[x];
	sum[idx]=sum[x];
	if(L[x]==1&&R[x]==cnth) rt[ver]=idx;
	if(id<=L[x]&&R[x]<=id){sum[idx]+=k;return;}
	int mid=(L[x]+R[x])/2;
	int now=idx;
	if(id<=mid) ls[now]=idx+1,update(id,ls[x],k,id);
	if(id>mid) rs[now]=idx+1,update(id,rs[x],k,id);
	pushup(now);
}
int getsum(int l,int r,int x)
{
	if(l>r) return 0;
	if(l<=L[x]&&R[x]<=r) return sum[x];
	int mid=(L[x]+R[x])/2;
	if(r<=mid) return getsum(l,r,ls[x]);
	if(l>mid) return getsum(l,r,rs[x]);
	return getsum(l,r,ls[x])+getsum(l,r,rs[x]);
}
int find(int x1,int x2,long long w1,long long w2,long long k,int pre1,int pre2)
{
	if(w1>w2) return -1;
	if(w1+(sum[x1]+pre1)*k<=w2+(sum[x2]+pre2)*k) return inf;
	if(L[x1]==R[x1]) return h[L[x1]];
	if(w1+(sum[ls[x1]]+pre1)*k>w2+(sum[ls[x2]]+pre2)*k) return find(ls[x1],ls[x2],w1,w2,k,pre1,pre2);
	return find(rs[x1],rs[x2],w1,w2,k,pre1+sum[ls[x1]],pre2+sum[ls[x2]]);
}
void print(int x)
{
	if(L[x]==R[x]){if(sum[x]) printf("(%d %d)",h[L[x]],sum[x]);return;}
	print(ls[x]);
	print(rs[x]);
}
int comp(int x,int y)
{
	int now=e[x].y;
	int tx=upper_bound(b+1,b+k+1,(nd){e[x].b,0})-b;
	int ty=upper_bound(b+1,b+k+1,(nd){e[y].b,0})-b;
//	printf("%d:%d %lld vs %d:%d %lld\n",x,tx,dis[x],y,ty,dis[y]);
	return find(rt[tx],rt[ty],dis[x],dis[y],a[now],0,0);
}
deque <int> hav[N];
void work(int id)
{
//	printf("work %d %d %d %d %d\n",e[id].x,e[id].y,e[id].a,e[id].b,e[id].w);
	int now=e[id].y;
	while(hav[now].size()>1&&comp(hav[now][hav[now].size()-2],hav[now].back())>=comp(hav[now].back(),id)) hav[now].pop_back();
	hav[now].push_back(id);
}
long long calc(int id)
{
	if(e[id].a==-1) return 0;
	int t=e[id].a,now=e[id].x;
	while(hav[now].size()>1&&comp(hav[now][0],hav[now][1])<t) hav[now].pop_front();
	if(hav[now].size()==0) return INF;
	int pos=hav[now][0];
	int tmpl=upper_bound(b+1,b+k+1,(nd){e[pos].b,0})-b;
	int tmpr=lower_bound(h+1,h+cnth+1,t)-h-1;
	int cnt=getsum(1,tmpr,rt[tmpl]);
	long long ret=dis[pos]+(long long)cnt*a[now]+e[id].w;
//	printf("calc %d %d %d %d %d:::%d ::%d %d %d %lld\n",e[id].x,e[id].y,e[id].a,e[id].b,e[id].w,pos,tmpl,tmpr,cnt,ret);
	return ret;
}
long long solve(int N,int M,int W,vector <int> T,vector <int> X,vector <int> Y,vector <int> A,vector <int> B,vector <int> C,vector <int> L,vector <int> R)
{
	n=N;m=M;k=W;
	for(int i=1;i<=n;i++) a[i-1]=T[i-1];
	for(int i=1;i<=m;i++) e[i]=e1[i]=e2[i]=(E){X[i-1],Y[i-1],A[i-1],B[i-1],C[i-1],i};
	m++;e[m]=e1[m]=e2[m]=(E){0,0,-1,0,0,m};
	m++;e[m]=e1[m]=e2[m]=(E){n-1,n-1,inf,inf+1,0,m};
	sort(e1+1,e1+m+1,cmp1);
	sort(e2+1,e2+m+1,cmp2);
	
	for(int i=1;i<=k;i++) b[i]=(nd){L[i-1],R[i-1]};
	k++;b[k]=(nd){0,0};
	sort(b+1,b+k+1);
	for(int i=1;i<=k;i++) h[i]=b[i].r;
	sort(h+1,h+k+1);h[0]=-1;
	for(int i=1;i<=k;i++) if(h[i]!=h[cnth]) h[++cnth]=h[i];
	for(int i=1;i<=k;i++) b[i].r=lower_bound(h+1,h+cnth+1,b[i].r)-h;
	rt[k+1]=++idx;build(1,cnth,1);
	for(int i=k;i>=1;i--) update(b[i].r,rt[i+1],1,i);
//	for(int i=1;i<=k;i++) printf("%d %d\n",b[i].l,b[i].r);
//	for(int i=1;i<=k+1;i++) printf("ver %d:",h[i]),print(rt[i]),printf("\n");
	
	int now=1;
	for(int i=1;i<=m;i++)
	{
		while(now<=m&&e2[now].b<=e1[i].a)
		{
			int id=e2[now].id;
			work(id);
			now++;
		}
		dis[e1[i].id]=calc(e1[i].id);
	}
	if(dis[m]>1e17) return -1;
	return dis[m];
}
//int main()
//{
//	int n,m,w;
//	vector <int> T,X,Y,A,B,C,L,R;
//	scanf("%d%d%d",&n,&m,&w);
//	for(int i=1;i<=n;i++)
//	{
//		int t;
//		scanf("%d",&t);
//		T.push_back(t);
//	}
//	for(int i=1;i<=m;i++)
//	{
//		int x,y,a,b,c;
//		scanf("%d%d%d%d%d",&x,&y,&a,&b,&c);
//		X.push_back(x);
//		Y.push_back(y);
//		A.push_back(a);
//		B.push_back(b);
//		C.push_back(c);
//	}
//	for(int i=1;i<=w;i++)
//	{
//		int l,r;
//		scanf("%d%d",&l,&r);
//		L.push_back(l);
//		R.push_back(r);
//	}
//	printf("%lld\n",solve(n,m,w,T,X,Y,A,B,C,L,R));
//}