#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const int maxm=1e5+10;
const int maxk=1e5+10;
const ll INF=1e18;

int n,m,k;
int t[maxn];
int x[maxm],y[maxm],a[maxm],b[maxm],c[maxm];
pair <int,int> v[maxk];

vector <int> ti; 

struct pers_seg{
	struct node{
		int l,r,ls,rs,sum;
	}t[(maxm*2+maxk*2)<<4];
	int rt[maxm*2+maxk*2];
	int cnt=0;
	int build(int l,int r){
		int u=++cnt;
		t[u].l=l;
		t[u].r=r;
		if(l==r){
			t[u].sum=0;
			return u;
		}
		int mid=(l+r)>>1;
		t[u].ls=build(l,mid);
		t[u].rs=build(mid+1,r);
		return u;
	}
	int modify(int u,int p){
		t[++cnt]=t[u];
		t[cnt].sum++;
		u=cnt;
		if(t[u].l==t[u].r){
			return u;
		}
		if(p<=t[t[u].ls].r)
			t[u].ls=modify(t[u].ls,p);
		else
			t[u].rs=modify(t[u].rs,p);
		return u;
	}
	int query(int u,int l,int r){
		//cout<<"query "<<u<<' '<<l<<' '<<r<<endl;
		if(l>r)
			return 0;
		if(l<=t[u].l&&t[u].r<=r)
			return t[u].sum;
		int ans=0;
		if(l<=t[t[u].ls].r)
			ans+=query(t[u].ls,l,r);
		if(t[t[u].rs].l<=r)
			ans+=query(t[u].rs,l,r);
		return ans;
	}
}ps;

void init(){
	for(int i=1;i<=m;i++){
		ti.push_back(a[i]);
		ti.push_back(b[i]);
	}
	for(int i=1;i<=k;i++){
		ti.push_back(v[i].first);
		ti.push_back(v[i].second);
	}
	sort(ti.begin(),ti.end());
	ti.resize(unique(ti.begin(),ti.end())-ti.begin());
	for(int i=1;i<=m;i++){
		a[i]=lower_bound(ti.begin(),ti.end(),a[i])-ti.begin()+1;
		b[i]=lower_bound(ti.begin(),ti.end(),b[i])-ti.begin()+1;
		//cout<<a[i]<<' '<<b[i]<<endl;
	}
	for(int i=1;i<=k;i++){
		v[i].first=lower_bound(ti.begin(),ti.end(),v[i].first)-ti.begin()+1;
		v[i].second=lower_bound(ti.begin(),ti.end(),v[i].second)-ti.begin()+1;
		//cout<<v[i].first<<' '<<v[i].second<<endl;
	}
	
	sort(v+1,v+k+1);
	ps.rt[0]=ps.build(1,ti.size());
	for(int i=1;i<=k;i++)
		ps.rt[v[i].first]=ps.modify(ps.rt[v[i-1].first],v[i].second);
	for(int i=1;i<=(int)ti.size();i++)
		if(ps.rt[i]==0)
			ps.rt[i]=ps.rt[i-1];
}

int count(int l,int r){//l<x,y<r
	return ps.query(ps.rt[ti.size()],1,r-1)-ps.query(ps.rt[l],1,r-1);	
}

struct oper{
	int tm,id;
	int type;// 0:query 1:modify
	friend bool operator<(const oper &x,const oper & y){
		if(x.tm==y.tm)
			return x.type>y.type;
		return x.tm<y.tm;
	}
};
vector <oper> op;

struct node{
	int p,l,r;
};
deque <node> q[maxn];
vector <int> p[maxn];
int pos[maxn];
ll f[maxm];
ll cal(int i,int j){
	return f[j]+(ll)count(b[j],a[i])*t[x[i]]+c[i];
}

ll solve(int N,int M,int K,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=K;
	if(m==0)
		return -1;
	for(int i=1;i<=n;i++)
		t[i]=T[i-1];
	for(int i=1;i<=m;i++){
		x[i]=X[i-1]+1;y[i]=Y[i-1]+1;a[i]=A[i-1];b[i]=B[i-1];c[i]=C[i-1];
	}
	for(int i=1;i<=k;i++)
		v[i]={L[i-1],R[i-1]};
	
	init();

	for(int i=1;i<=m;i++){
		op.push_back({a[i],i,0});
		op.push_back({b[i],i,1});
	}
	sort(op.begin(),op.end());
	
	p[1].push_back(0);
	for(oper z:op){
		int i=z.id,u;
		if(z.type==0){
			u=x[i];
			p[u].push_back(i);
		}
	}
	q[1].push_back({0,0,(int)p[1].size()-1});
	for(int i=1;i<=n;i++)
		pos[i]=-1;
	pos[1]=0;
	for(int i=1;i<=m;i++)
		f[i]=INF;
	for(oper z:op){
		int i=z.id,u;
		if(z.type==0){
			u=x[i];
			pos[u]++;
			if(q[u].empty()){
				f[i]=INF;
				continue;
			}
			while(q[u].front().r<pos[u])
				q[u].pop_front();
			int j=q[u].front().p;
			f[i]=cal(i,j);
			q[u].front().l=pos[u];
		}
		else{
			u=y[i];
			if(q[u].empty()){
				if(pos[u]!=(int)p[u].size()-1)
					q[u].push_back({i,pos[u]+1,(int)p[u].size()-1});
				continue;
			}
			while(q[u].size()>1&&cal(p[u][q[u].back().l],i)<=cal(p[u][q[u].back().l],q[u].back().p))
				q[u].pop_back();
			int l=q[u].back().l,r=q[u].back().r,mid,t=r+1;
			while(l<=r){
				mid=(l+r)>>1;
//				cout<<"lmr"<<' '<<l<<' '<<mid<<' '<<r<<' '<<p[u][mid]<<endl;
				if(cal(p[u][mid],i)<=cal(p[u][mid],q[u].back().p)){
					t=mid;
					r=mid-1;
				}
				else
					l=mid+1;
			}
//			cout<<"t "<<t<<endl;
			if(t<=(int)p[u].size()-1){
				q[u].back().r=t-1;
				q[u].push_back({i,t,(int)p[u].size()-1});
			}
		}
	}
//	for(int i=1;i<=m;i++)cout<<f[i]<<' ';cout<<endl; 
	ll ans=INF;
	for(int i=1;i<=m;i++)
		if(y[i]==n)
			ans=min(ans,f[i]+(ll)count(b[i],ti.size()+1)*t[n]);
	
	if(ans==INF)
		ans=-1;
	return ans;
}