#include "train.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2*1e5;
struct T{
int le=-1,ri=-1;
int sum=0;
};
T TT(T le,T ri){
T pa;
pa.sum=le.sum+ri.sum;
return pa;
}
T Tid;
vector<T> seg;
int init(int le,int ri){
int v=seg.size();
seg.push_back(Tid);
if(le==-1){
seg[v].sum=ri;
}
else{
seg[v]=TT(seg[le],seg[ri]);
seg[v].le=le,seg[v].ri=ri;
}
return v;
}
int build(int TL,int TR){
if(TL==TR){
return init(-1,0);
}
int TM=((TL+TR)>>1);
return init(build(TL,TM),build(TM,TR));
}
int update(int v,int TL,int TR,int i){
if(TL==TR){
return init(-1,seg[v].sum+1);
}
int TM=((TL+TR)>>1);
if(i<=TM){
return init(update(seg[v].le,TL,TM,i),seg[v].ri);
}
return init(seg[v].le,update(seg[v].ri,TM+1,TR,i));
}
T query(int v,int TL,int TR,int l,int r){
if(l>TR||r<TL){
return Tid;
}
if(l<=TL&&TR<=r){
return seg[v];
}
int TM=((TL+TR)>>1);
return TT(query(seg[v].le,TL,TM,l,r),query(seg[v].ri,TM+1,TR,l,r));
}
int walk(int vl,int vr,int TL,int TR,int k){
if(TL==TR){
return TL;
}
int TM=((TL+TR)>>1);
if(seg[seg[vr].le].sum-seg[seg[vl].le].sum>=k){
return walk(seg[vl].le,seg[vr].le,TL,TM,k);
}
return walk(seg[vl].ri,seg[vr].ri,TM+1,TR,k-(seg[seg[vr].le].sum-seg[seg[vl].le].sum));
}
struct event{
int cmp,idxu,idxq;
};
bool cmp(event &a,event &b){
if(a.cmp!=b.cmp){
return (a.cmp<b.cmp);
}
return (a.idxu<b.idxu);
}
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){
vector<int> root(w+1);
vector<int> val(w);
vector<event> que(m+w);
for(int i=0;i<m;i++){
que[i]={b[i],-1,i};
}
for(int i=0;i<w;i++){
que[m+i]={r[i],i,-1};
}
sort(que.begin(),que.end(),cmp);
for(int i=0;i<que.size();i++){
if(que[i].idxq!=-1){
val[que[i].idxq]=i;
}
}
vector<pair<int,int>> order(w+1);
order[0]={-1,-1};
for(int i=0;i<w;i++){
order[i+1]={l[i],i};
}
sort(order.begin(),order.end());
root[0]=build(0,m+w-1);
for(int i=1;i<=w;i++){
root[i]=update(root[i-1],0,m+w-1,val[order[i].second]);
}
long long DP[m+1];
memset(DP,-1,sizeof(DP));
DP[m]=0;
vector<set<pair<int,int>>> se(n);
se[0].insert({-1,m});
bool del[m+1]={false};
vector<vector<pair<int,int>>> group(m+w);
x.push_back(0);
y.push_back(0);
a.push_back(-1);
b.push_back(-1);
c.push_back(0);
long long ans=1e18;
for(int i=0;i<m+w;i++){
for(pair<int,int> &x:group[i]){
if(!del[x.first]&&!del[x.second]){
int u=y[x.first];
int idx=x.first;
while(true){
del[idx]=true;
set<pair<int,int>>::iterator it,itr;
it=se[u].find({b[idx],idx});
itr=it,itr++;
idx=(*itr).second;
se[u].erase(it);
itr=se[u].find({b[idx],idx});
if(itr==se[u].begin()){
break;
}
it=itr,it--;
idx=(*it).second;
int idx2=(*itr).second;
int cnt=(DP[idx2]-DP[idx]+t[u]-1)/t[u];
int le=lower_bound(order.begin(),order.end(),make_pair(b[idx]+1,-1))-order.begin()-1;
int ri=upper_bound(order.begin(),order.end(),make_pair(b[idx2],m+w+1))-order.begin()-1;
if(seg[ri].sum-seg[le].sum<cnt){
break;
}
if(DP[idx2]>=DP[idx]){
continue;
}
int tim=walk(le,ri,0,m+w-1,cnt);
if(tim<=i){
continue;
}
group[tim].push_back({idx,idx2});
break;
}
}
}
if(que[i].idxq!=-1){
int idx,idx2=que[i].idxq;
idx=(*se[x[idx2]].begin()).second;
int le=lower_bound(order.begin(),order.end(),make_pair(b[idx]+1,-1))-order.begin()-1;
int ri=upper_bound(order.begin(),order.end(),make_pair(a[idx2]-1,m+w+1))-order.begin()-1;
le--;
DP[idx2]=DP[idx]+c[idx2]+1LL*t[x[idx2]]*max(0,query(root[ri],0,m+w-1,0,i).sum-query(root[le],0,m+w-1,0,i).sum);
if(y[idx2]==n-1){
int need=upper_bound(order.begin(),order.end(),make_pair(b[idx2],m+w+1))-order.begin();
need=order.size()-need;
ans=min(ans,DP[idx2]+1LL*need*t[y[idx2]]);
}
int u=y[idx2];
se[u].insert({b[idx2],idx2});
set<pair<int,int>>::iterator it,itr;
itr=se[u].find({b[idx2],idx2});
if(itr==se[u].begin()){
continue;
}
it=itr,it--;
idx=(*it).second;
idx2=(*itr).second;
int cnt=(DP[idx2]-DP[idx]+t[u]-1)/t[u];
le=lower_bound(order.begin(),order.end(),make_pair(b[idx]+1,-1))-order.begin()-1;
ri=upper_bound(order.begin(),order.end(),make_pair(b[idx2],m+w+1))-order.begin()-1;
bool flag=false;
if(seg[ri].sum-seg[le].sum<cnt){
continue;
}
if(DP[idx2]>=DP[idx]){
flag=true;
}
else{
int tim=walk(le,ri,0,m+w-1,cnt);
if(tim<=i){
flag=true;
}
else{
group[tim].push_back({idx,idx2});
}
}
if(flag){
while(true){
del[idx]=true;
set<pair<int,int>>::iterator it,itr;
it=se[u].find({b[idx],idx});
itr=it,itr++;
idx=(*itr).second;
se[u].erase(it);
itr=se[u].find({b[idx],idx});
if(itr==se[u].begin()){
break;
}
it=itr,it--;
idx=(*it).second;
int idx2=(*itr).second;
int cnt=(DP[idx2]-DP[idx]+t[u]-1)/t[u];
int le=lower_bound(order.begin(),order.end(),make_pair(b[idx]+1,-1))-order.begin()-1;
int ri=upper_bound(order.begin(),order.end(),make_pair(b[idx2],m+w+1))-order.begin()-1;
if(seg[ri].sum-seg[le].sum<cnt){
break;
}
if(DP[idx2]>=DP[idx]){
continue;
}
int tim=walk(le,ri,0,m+w-1,cnt);
if(tim<=i){
continue;
}
group[tim].push_back({idx,idx2});
break;
}
}
}
}
return ans;
}
