#include "train.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;
namespace{
const ll mxN=6e5+5;
const ll inf=1e18;
ll n, m, w;
vll t, x, y, a, b, c, l, r;
vll con;
vll in[mxN], out[mxN];
deque<ll> dq[mxN];
ll dp[mxN];
ll id(ll tar){
return lower_bound(con.begin(), con.end(), tar)-con.begin();
}
ll f(ll idx, ll time){
if(dp[idx]==inf) return inf;
ll re=dp[idx];
for(ll i=0;i<w;i++){
if(l[i]>b[idx] && r[i]<time){
re+=t[y[idx]];
}
}
return re;
}
ll inter(ll idx1, ll idx2){
ll lef=id(b[idx2]), rig=(ll) con.size()-1;
ll re=inf;
while(lef<=rig){
ll mid=(lef+rig)/2;
if(f(idx1, con[mid])>=f(idx2, con[mid])){
re=con[mid];
rig=mid-1;
}
else{
lef=mid+1;
}
}
return re;
}
}
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) {
con.clear();
n=N;
m=M;
w=W;
t=vll(n, 0);
for(ll i=0;i<n;i++){
t[i]=T[i];
}
x=vll(m+1, 0);
for(ll i=0;i<m;i++){
x[i]=X[i];
}
y=vll(m+1, 0);
for(ll i=0;i<m;i++){
y[i]=Y[i];
}
a=vll(m+1, 0);
for(ll i=0;i<m;i++){
a[i]=A[i];
con.pb(a[i]);
}
b=vll(m+1, 0);
for(ll i=0;i<m;i++){
b[i]=B[i];
con.pb(b[i]);
}
c=vll(m+1, 0);
for(ll i=0;i<m;i++){
c[i]=C[i];
}
l=vll(w, 0);
for(ll i=0;i<w;i++){
l[i]=L[i];
con.pb(l[i]);
}
r=vll(w, 0);
for(ll i=0;i<w;i++){
r[i]=R[i];
con.pb(r[i]);
}
con.pb(0);
sort(con.begin(), con.end());
con.erase(unique(con.begin(), con.end()), con.end());
x[m]=0;
y[m]=0;
a[m]=0;
b[m]=0;
c[m]=0;
dp[m]=0;
for(ll i=0;i<m;i++){
in[id(a[i])].pb(i);
out[id(b[i])].pb(i);
}
dq[id(0)].pb(m);
for(ll i=0;i<(ll) con.size();i++){
for(auto &it:out[i]){
if(dp[it]==inf) continue;
ll tar=y[it];
while((ll) dq[tar].size()>=2 && inter(dq[tar][(ll) dq[tar].size()-2], it)<=
inter(dq[tar][(ll) dq[tar].size()-2], dq[tar][(ll) dq[tar].size()-1])){
dq[tar].pop_back();
}
if(dq[tar].empty() || inter(dq[tar][(ll) dq[tar].size()-1], it)!=inf){
dq[tar].pb(it);
}
}
for(auto &it:in[i]){
ll tar=x[it];
if(dq[tar].empty()){
dp[it]=inf;
continue;
}
while((ll) dq[tar].size()>=2 && f(dq[tar][1], a[it])<=
f(dq[tar][0], a[it])){
dq[tar].pop_front();
}
dp[it]=f(dq[tar][0], a[it])+c[it];
dp[it]=min(dp[it], inf);
}
}
ll ans=inf;
for(ll i=0;i<m;i++){
// cout<<i<<' '<<dp[i]<<'\n';
if(y[i]==n-1){
ans=min(ans, f(i, inf));
}
}
if(ans==inf) return -1;
return ans;
}
