#include<bits/stdc++.h>
#define MAXN 1000007
using namespace std;
const long long inf=1e18;
const int endt=1e9;
struct flight{
int from,to;
int l,r,cost;
inline friend bool operator < (flight fr,flight sc){
return fr.l<sc.l;
}
}s[MAXN];
struct meal{
int l,r;
}w[MAXN];
int n,m,k;
long long cost[MAXN];
long long dp[MAXN];
priority_queue< pair<int,long long> , vector< pair<int,long long> > , greater< pair<int,long long> > > endf[MAXN];
long long meals(int l,int r){
int res=0;
for(int i=1;i<=k;i++){
if(w[i].l>=l and w[i].r<=r)res++;
}
return res;
}
struct CHT{
struct state{
long long bias;
int l,from;
};
vector<state> v;
long long coef;
bool better(state a,state b,int x){
if(x<a.l)return false;
return a.bias + meals(a.l,x)*coef < b.bias + meals(b.l,x)*coef;
}
int intersect(state a,state b){
int l=max(a.l,b.l)-1,r=endt,tt;
while(l+1<r){
tt=(l+r)/2;
if(a.bias + meals(a.l,tt)*coef <= b.bias + meals(b.l,tt)*coef)l=tt;
else r=tt;
}
return r;
}
void add(state s){
if(!v.empty() and v.back().bias + meals(v.back().l,endt)*coef <= s.bias + meals(s.l,endt)*coef)return;
while(!v.empty() and better(s,v.back(),v.back().from))v.pop_back();
if(v.empty())v.push_back({s.bias,s.l,s.l});
else v.push_back({s.bias,s.l,intersect(v.back(),s)});
}
long long query(int x){
if(v.empty() or x<v[0].l)return inf;
int l=0,r=v.size(),tt;
while(l+1<r){
tt=(l+r)/2;
if(v[tt].from<=x){
l=tt;
}else{
r=tt;
}
}
return v[l].bias + meals(v[l].l,x) * coef;
}
}cht[MAXN];
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++){
cost[i]=T[i-1];
cht[i].coef=cost[i];
}
for(int i=1;i<=m;i++){
s[i]={X[i-1]+1,Y[i-1]+1,A[i-1],B[i-1],C[i-1]};
}
for(int i=1;i<=k;i++)w[i]={L[i-1],R[i-1]};
sort(s+1,s+m+1);
cht[1].add({0,0,0});
for(int i=1;i<=m;i++){
dp[i]=inf;
while(!endf[s[i].from].empty() and endf[s[i].from].top().first<=s[i].l){
auto curr=endf[s[i].from].top();
cht[s[i].from].add({curr.second,curr.first,0});
endf[s[i].from].pop();
}
long long mindp=cht[s[i].from].query(s[i].l-1);
dp[i]=mindp+s[i].cost;
endf[s[i].to].push({s[i].r,dp[i]});
}
long long ans=inf;
for(int i=1;i<=m;i++){
if(s[i].to!=n)continue;
ans=min(ans , dp[i] + meals(s[i].r+1,endt) * cost[n]);
}
if(ans>=inf)return -1;
return ans;
}
/*int main(){
cout<<solve(3, 3, 1, {20, 30, 40}, {0, 1, 0}, {1, 2, 2},
{1, 20, 18}, {15, 30, 40}, {10, 5, 40}, {16}, {19})<<"\n";
cout<<solve(3, 5, 6, {30, 38, 33}, {0, 1, 0, 0, 1}, {2, 0, 1, 2, 2},
{12, 48, 26, 6, 49}, {16, 50, 28, 7, 54}, {38, 6, 23, 94, 50},
{32, 14, 42, 37, 2, 4}, {36, 14, 45, 40, 5, 5})<<"\n";
return 0;
}*/
