#include "train.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
#define f first
#define s second
#define eb emplace_back
#define sz(x) (int)x.size()
#define add(x,y) ((x+y)%md)
#define Add(x,y) (x=add(x,y))
#define mul(x,y) ((x*y)%md)
#define Mul(x,y) (x=mul(x,y))
template<class T> T chmn(T &x,T y){ return x=min(x,y); }
template<class T> T chmx(T &x,T y){ return x=max(x,y); }
const int inf=1e9;
const ll linf=1e18;
const ll md=1e9+7;
struct segment{
struct node{
node *l,*r;
int x;
node(int x=0):x(x),l(l),r(r){}
};
using pnode=node*;
vector<pnode> rt;
int l0,r0;
void init(int n,int l,int r){
rt.resize(n+5);
l0=l,r0=r;
build(rt[0],l0,r0);
}
void build(pnode &t,int il,int ir){
t=new node();
if(il>=ir) return;
int mid=il+ir>>1;
build(t->l,il,mid), build(t->r,mid+1,ir);
}
void upd(int t0,int t1,int id,int x){ upd(rt[t0],rt[t1],l0,r0,id,x); }
void upd(pnode t0,pnode &t1,int il,int ir,int id,int x){
t1=new node(*t0);
t1->x+=x;
if(il>=ir) return;
int mid=il+ir>>1;
if(id<=mid) upd(t0->l,t1->l,il,mid,id,x);
else upd(t0->r,t1->r,mid+1,ir,id,x);
}
int qr(int t,int l,int r){ return qr(rt[t],l0,r0,l,r); }
int qr(pnode t,int il,int ir,int l,int r){
if(il>r||ir<l) return 0;
if(l<=il&&ir<=r) return t->x;
int mid=il+ir>>1;
return qr(t->l,il,mid,l,r)+qr(t->r,mid+1,ir,l,r);
}
}t;
vector<pair<ll,pii>> dp[100005];
int R[100005];
vector<int> Lcmp;
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_) {
vector<int> v(W);
iota(v.begin(),v.end(),0);
sort(v.begin(),v.end(),[&](const int &l,const int &r){ return R_[l]<R_[r]; });
for(int i=0;i<W;++i) Lcmp.eb(L_[i]);
sort(Lcmp.begin(),Lcmp.end());
Lcmp.erase(unique(Lcmp.begin(),Lcmp.end()),Lcmp.end());
t.init(W+5,0,sz(Lcmp));
for(int i=0;i<W;++i){
R[i]=R_[v[i]];
t.upd(i,i+1,lower_bound(Lcmp.begin(),Lcmp.end(),L_[v[i]])-Lcmp.begin(),1);
}
dp[0].eb(0,pii(-1,0));
v.resize(M);
iota(v.begin(),v.end(),0);
sort(v.begin(),v.end(),[&](const int &l,const int &r){ return B[l]==B[r] ? A[l]<A[r] : B[l]<B[r]; });
for(auto &i:v){
int ver = lower_bound(R,R+W,A[i])-R;
int l=-1,r=sz(dp[X[i]])-1;
while(l<r){
int mid=l+r+1>>1;
if(dp[X[i]][mid].s.s>ver) r=mid-1;
else l=mid;
}
if(l!=-1){
int id = upper_bound(Lcmp.begin(),Lcmp.end(),dp[X[i]][l].s.f)-Lcmp.begin();
ll cost = C[i] + dp[X[i]][l].f + (ll)T[X[i]]*t.qr(ver,id,sz(Lcmp));
ver = lower_bound(R,R+W,B[i])-R;
while(!dp[Y[i]].empty() && dp[Y[i]].back().s.s>=ver){
ll c0 = dp[Y[i]].back().f - (ll)T[Y[i]]*t.qr(dp[Y[i]].back().s.s,0,upper_bound(Lcmp.begin(),Lcmp.end(),dp[Y[i]].back().s.f)-Lcmp.begin()-1);
ll c1 = cost - (ll)T[Y[i]]*t.qr(dp[Y[i]].back().s.s,0,upper_bound(Lcmp.begin(),Lcmp.end(),B[i])-Lcmp.begin()-1);
if(c0<c1) break;
dp[Y[i]].pop_back();
}
if(dp[Y[i]].empty()) dp[Y[i]].eb(cost,pii(B[i],ver));
else{
l=max(ver,dp[Y[i]].back().s.s), r=W+1;
while(l<r){
int mid=l+r>>1;
ll c0 = dp[Y[i]].back().f - (ll)T[Y[i]]*t.qr(mid,0,upper_bound(Lcmp.begin(),Lcmp.end(),dp[Y[i]].back().s.f)-Lcmp.begin()-1);
ll c1 = cost - (ll)T[Y[i]]*t.qr(mid,0,upper_bound(Lcmp.begin(),Lcmp.end(),B[i])-Lcmp.begin()-1);
if(c0>c1) r=mid;
else l=mid+1;
}
if(l!=W+1) dp[Y[i]].eb(cost,pii(B[i],l));
}
}
}
if(dp[N-1].empty()) return -1;
ll res=1e18;
for(auto &[c,b]:dp[N-1]){
int id=upper_bound(Lcmp.begin(),Lcmp.end(),b.f)-Lcmp.begin();
chmn(res,c+(ll)T[N-1]*t.qr(W,id,sz(Lcmp)));
}
return res;
}
