#include "train.h"
#include<bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define forf(i,s,e) for(int i = s; i<=e; i++)
#define forb(i,s,e) for(int i = s; i>=e; i--)
#define idx(i,v) lower_bound(all(v),i)-v.begin()
#define comp(v) v.erase(unique(all(v)),v.end())
#define fs first
#define se second
#define sz(v) (int)v.size()
#define SPACE << " " <<
#define LINE << "\n"
using namespace std;
typedef long long ll;
ll inf = 4e18;
int N,M,W,S;
vector<ll> CS;
vector<int> tx;
struct Node{
int v,l,r;
} def = {0,0,0};
struct PST{
int rt[400001];
vector<int> root = {0};
vector<Node> node = {def};
void update(int now, int prv, int s, int e, int f, int x){
if(s==e){node[now].v = node[prv].v+x; return;}
int m = s+e>>1;
if(f<=m){
node[now].l = node.size(); node.push_back(def);
node[now].r = node[prv].r;
update(node[now].l,node[prv].l,s,m,f,x);
}
else{
node[now].r = node.size(); node.push_back(def);
node[now].l = node[prv].l;
update(node[now].r,node[prv].r,m+1,e,f,x);
}
node[now].v = node[node[now].l].v + node[node[now].r].v;
}
int query(int now , int prv, int s, int e,int l ,int r){
if(l<=s && e<=r) return node[now].v-node[prv].v;
if(r<s || l>e) return 0;
int m = s+e>>1;
return query(node[now].l,node[prv].l,s,m,l,r)+query(node[now].r,node[prv].r,m+1,e,l,r);
}
int bin(int now, int prv, int s, int e, ll k){
if(s==e){
if(k <= node[now].v - node[prv].v) return s;
else return s+1;
}
int tmp = node[node[now].l].v - node[node[prv].l].v;
int m =s+e>>1;
if(k <= tmp) return bin(node[now].l, node[prv].l,s,m,k);
else return bin(node[now].r, node[prv].r, m+1,e,k-tmp);
}
} pst;
struct Line{
ll idx,s,st, c;
ll eval(ll e) const{
if(e == s) return c;
return c+CS[idx]*pst.query(pst.rt[e-1], pst.rt[s], 1,S, 1,e-1);
}
};
int cross(Line x, Line y){
if(x.eval(y.s) > y.eval(y.s)) return y.s;
ll k = (y.c - x.c) / CS[y.idx] + 1;
return pst.bin(pst.rt[y.s], pst.rt[x.s], 1, S, k)+1;
}
vector<int> pos[400001];
deque<Line> Q[400001];
vector<Line> ins[400001];
vector<array<ll,4> > upd[400001];
long long solve(int N, int M, int W, std::vector<int> T, std::vector<int> X, std::vector<int> Y,
std::vector<int> A, std::vector<int> B, std::vector<int> C, std::vector<int> L,
std::vector<int> R) {
::N=N, ::M=M, ::W=W;
forf(i,0,N-1) CS.pb(T[i]);
forf(i,0,M-1) tx.pb(A[i]), tx.pb(B[i]); forf(i,0,W-1) tx.pb(L[i]), tx.pb(R[i]);
sort(all(tx)), comp(tx); S = sz(tx);
forf(i,0,M-1) A[i] = idx(A[i],tx)+1, B[i] = idx(B[i],tx)+1; forf(i,0,W-1) L[i] = idx(L[i],tx)+1, R[i] = idx(R[i],tx)+1, pos[L[i]].pb(R[i]);
forf(i,0,M-1) upd[A[i]].pb({X[i],Y[i],B[i],C[i]});
forf(i,1,S){
for(auto j : pos[i]){
pst.root.pb(sz(pst.node)), pst.node.pb(def);
pst.update(pst.root.back(),pst.root[sz(pst.root)-2],1,S,j,1);
}
pst.rt[i] = pst.root.back();
}
Q[0].pb({0,0,0,0}); forf(i,1,N-1) Q[i].pb({0,0,0,inf});
forf(t,1,S){
for(auto now : ins[t]){
int idx = now.idx;
while(sz(Q[idx]) >= 2 && Q[idx].back().st >= cross(Q[idx].back(),now)) Q[idx].pop_back();
now.st = cross(Q[idx].back(),now);
Q[idx].pb(now);
}
for(auto [s,e,et,c] : upd[t]){
while(sz(Q[s]) >= 2 && Q[s][1].st <= t) Q[s].pop_front();
ll cst = Q[s].front().eval(t) + c;
ins[et].pb({e,et,et,cst});
}
}
while(sz(Q[N-1]) >= 2 && Q[N-1][1].st <= S+1) Q[N-1].pop_front();
if(Q[N-1].front().eval(S+1) >= inf) return -1;
return Q[N-1].front().eval(S+1);
}
