#include "train.h"
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
const int M=(1<<19)+2e6;
int tW;
vector<int> tT;
vector<int> cn(1,0),tcn;
struct UWU{
int now=0,sz;
struct node{
int l,r,val;
};
vector<node> s;
vector<int> arr,rt;
int cp(int u){s[++now]=s[u]; return now;}
void init(){
s.resize(M);
arr.resize(N);
rt.resize(N);
}
void build(int l,int r,int idx){
now=max(now,idx);
if(l==r){
s[idx].val=s[idx].l=s[idx].r=0;
return;
}
int m=(l+r)/2;
build(l,m,idx*2);
build(m+1,r,idx*2+1);
s[idx].l=idx*2,s[idx].r=idx*2+1;
s[idx].val=0;
}
int update(int l,int r,int idx,int a){
if(a<l || a>r) return idx;
int u=cp(idx);
if(l==r){
s[u]={0,0,s[u].val+1};
return u;
}
int m=(l+r)/2;
if(a<=m) s[u].l=update(l,m,s[idx].l,a);
else s[u].r=update(m+1,r,s[idx].r,a);
s[u].val=s[s[u].l].val+s[s[u].r].val;
return u;
}
void prep(int n){
build(1,n,1);
sz=n;
rt[0]=1;
for(int i=1;i<=n;i++) rt[i]=update(1,n,rt[i-1],arr[i]);
}
int squery(int l,int r,int il,int ir,int k){
if(l==r) return l;
int m=(l+r)/2;
int lt=s[s[ir].l].val-s[s[il].l].val;
if(lt<=k) return squery(l,m,s[il].l,s[ir].l,k);
return squery(m+1,r,s[il].r,s[ir].r,k-lt);
}
int query(int l,int r,int idx,int a,int b){
if(a>r || b<l) return 0;
if(a<=l && b>=r) return s[idx].val;
int m=(l+r)/2;
return query(l,m,s[idx].l,a,b)+query(m+1,r,s[idx].r,a,b);
}
int ask(int l,int r,int k){
return cn[arr[squery(1,sz,rt[l],rt[r+1],k)]];
}
int cnt(int l,int r,int x){
return query(1,sz,rt[r],1,x)-query(1,sz,rt[l-1],1,x);
}
}hode;
deque<pair<long long,int>> dist[N];
priority_queue<tuple<int,long long,int>,vector<tuple<int,long long,int>>,greater<tuple<int,long long,int>>> D;
set<pair<int,int>> out;
int req[N];
int fi(int x){return lower_bound(cn.begin(),cn.end(),x)-cn.begin();}
int fiL(int x){return upper_bound(tcn.begin(),tcn.end(),x)-tcn.begin();}
long long cal(long long oD,long long nD,long long tu){
return (nD-oD+tu-1)/tu;
}
void Creq(int u){
if(dist[u].empty()) return;
if(dist[u].size()==1){
out.erase({req[u],u});
req[u]=INT_MAX;
return;
}
auto [df,bf]=dist[u].front();
auto [ds,bs]=*(dist[u].begin()+1);
int use=cal(df,ds,tT[u]);
int pl=fiL(bf);
if(tW-pl>use){
out.erase({req[u],u});
req[u]=2e9;
out.insert({req[u],u});
return;
}
out.erase({req[u],u});
req[u]=hode.ask(pl,tW-1,use);
out.insert({req[u],u});
}
void upd(int id,int x,int b){
while(!dist[id].empty() && dist[id].back().first>=x) dist[id].pop_back();
dist[id].push_back({x,b});
Creq(id);
}
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) {
tW=W;
tT=T;
vector<tuple<int,int,int,int,int>> E;
vector<pair<int,int>> Z;
for(int i=0;i<N;i++) req[i]=INT_MAX;
for(int i=0;i<M;i++){
E.push_back({A[i],B[i],C[i],X[i],Y[i]});
}
sort(E.begin(),E.end());
for(int i=0;i<W;i++){
Z.push_back({L[i],R[i]});
cn.push_back(R[i]);
tcn.push_back(L[i]);
}
sort(Z.begin(),Z.end());
sort(cn.begin(),cn.end());
sort(tcn.begin(),tcn.end());
cn.erase(unique(cn.begin(),cn.end()),cn.end());
hode.init();
for(int i=0;i<W;i++) hode.arr[i+1]=fi(Z[i].second);
// cout<<"init";
// for(int i=1;i<=W;i++) cout<<hode.arr[i] <<" ";
// cout<<"\n";
hode.prep(W);
dist[0].push_back({0,0});
for(auto [a,b,c,x,y]:E){
//cout<<a <<" " <<b <<" " <<c <<" " <<x <<" " <<y <<"\n";
while(!D.empty() && get<0>(D.top())<=a){
auto [bi,di,ui]=D.top();
D.pop();
upd(ui,di,bi);
//cout<<"in" <<ui <<" " <<di <<" " <<bi <<"\n";
}
while(!out.empty() && out.begin()->first<=a){
dist[out.begin()->second].pop_front();
Creq(out.begin()->second);
}
if(dist[x].empty()) continue;
auto [di,bi]=dist[x].front();
int pl=fiL(bi)+1;
int fd=lower_bound(cn.begin(),cn.end(),a)-cn.begin()-1;
//cout<<pl <<" " <<fd <<"\n";
long long ca=(fd!=0)?hode.cnt(pl,W,fd):0;
long long fval=di+ca*(long long)T[x]+(long long)c;
D.push({b,fval,y});
// cout<<"got" <<di <<" " <<cal <<" " <<c <<"\n";
// cout<<"cand" <<b <<" " <<fval <<" " <<y <<"\n";
}
while(!D.empty()){
auto [bi,di,ui]=D.top();
D.pop();
upd(ui,di,bi);
}
if(dist[N-1].empty()) return -1;
long long ans=LLONG_MAX;
while(!dist[N-1].empty()){
//cout<<"hi";
auto [di,bi]=dist[N-1].front();
dist[N-1].pop_front();
int pl=fiL(bi);
int cal=hode.cnt(pl+1,W,W);
long long fval=di+cal*T[N-1];
//cout<<"F" <<fval <<"\n";
ans=min(ans,fval);
}
return ans;
}
