//APIO 2024 Train
//https://qoj.ac/contest/1684/problem/8725
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
const int BLOCK = 2000;
struct Fenwick{
vll bit; ll sz;
Fenwick(ll n){bit.assign(n+2,0); sz=n;}
void Add(ll pos,ll delta){pos++; for(; pos<=sz; pos+=pos&-pos) bit[pos]+=delta;}
ll Query(ll pos){
ll res=0; pos++;
for(; pos>0; pos-=pos&-pos) res+=bit[pos];
return res;
}
};
struct LazySegtree{
vll tree, lazy; ll sz, cnt;
LazySegtree(ll n,ll n2){
sz=1; while(sz<n) sz*=2;
cnt=n2; tree.assign(cnt*2*sz,1e18); lazy.assign(cnt*2*sz,0);
}
void apply(ll id,ll delta,ll x){tree[id*2*sz+x]+=delta; lazy[id*2*sz+x]+=delta;}
void push(ll id,ll x,ll lx,ll rx){
if(lazy[id*2*sz+x]==0 || rx-lx==1) return;
apply(id,lazy[id*2*sz+x],2*x+1); apply(id,lazy[id*2*sz+x],2*x+2); lazy[id*2*sz+x]=0;
}
void Add(ll id,ll l,ll r,ll delta,ll x,ll lx,ll rx){
if(rx<=l || r<=lx) return;
if(l<=lx && rx<=r){apply(id,delta,x); return;}
push(id,x,lx,rx); ll m=(lx+rx)/2;
Add(id,l,r,delta,2*x+1,lx,m); Add(id,l,r,delta,2*x+2,m,rx);
tree[id*2*sz+x]=min(tree[id*2*sz+2*x+1],tree[id*2*sz+2*x+2]);
}
void Add(ll id,ll l,ll r,ll delta){Add(id,l,r,delta,0,0,sz);}
ll Query(ll id,ll l,ll r,ll x,ll lx,ll rx){
if(rx<=l || r<=lx) return 1e18;
if(l<=lx && rx<=r) return tree[id*2*sz+x];
push(id,x,lx,rx); ll m=(lx+rx)/2;
return min(Query(id,l,r,2*x+1,lx,m),Query(id,l,r,2*x+2,m,rx));
}
ll Query(ll id,ll l,ll r){return Query(id,l,r,0,0,sz);}
void Set(ll id,ll pos,ll delta){Add(id,pos,pos+1,min(0ll,delta-Query(id,pos,pos+1)));}
};
ll 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){
vll V={0}; auto comp=[&](ll x){return lower_bound(V.begin(),V.end(),x)-V.begin();};
for(int i=0; i<m; i++) V.push_back(A[i]), V.push_back(B[i]);
for(int i=0; i<w; i++) V.push_back(L[i]), V.push_back(R[i]);
sort(V.begin(),V.end()); V.erase(unique(V.begin(),V.end()),V.end());
for(int i=0; i<m; i++) A[i]=comp(A[i]), B[i]=comp(B[i]);
for(int i=0; i<w; i++) L[i]=comp(L[i]), R[i]=comp(R[i]);
vll cnt(n,0), ID(n,-1), nodes; cnt[0]=1; ll cur=0;
for(int i=0; i<m; i++) cnt[Y[i]]++;
for(int i=0; i<n; i++) if(cnt[i]>BLOCK) ID[i]=cur++, nodes.push_back(i);
ll ans=1e18; Fenwick light(V.size()); LazySegtree heavy(V.size(),cur);
vector<pair<ll,ll>> states[n], cand[V.size()]; states[0].push_back({0,0});
vll ranges[V.size()]; vector<array<ll,4>> edges[V.size()];
for(int i=0; i<m; i++) edges[A[i]].push_back({X[i],Y[i],B[i],C[i]});
for(int i=0; i<w; i++) ranges[R[i]].push_back(L[i]);
if(ID[0]!=-1) heavy.Set(ID[0],0,0);
for(int i=1; i<(ll)V.size(); i++){
for(auto [v,cost]:cand[i]){
if(cnt[v]<=BLOCK) states[v].push_back({cost,i});
else heavy.Set(ID[v],i,cost);
}
for(auto [v,u,nTime,costEdge]:edges[i]){
ll best=1e18;
if(cnt[v]<=BLOCK){
for(auto [cost,time]:states[v]) best=min(best,cost+costEdge+T[v]*light.Query(time));
}else best=heavy.Query(ID[v],0,(ll)V.size())+costEdge;
cand[nTime].push_back({u,best});
}
for(auto l:ranges[i]){
light.Add(0,1); light.Add(l,-1);
for(auto v:nodes) heavy.Add(ID[v],0,l,T[v]);
}
}
if(cnt[n-1]<=BLOCK){
for(auto [cost,time]:states[n-1]) ans=min(ans,cost+T[n-1]*light.Query(time));
}else ans=heavy.Query(ID[n-1],0,(ll)V.size());
return (ans!=1e18?ans:-1);
}
