#include <bits/stdc++.h>
#include "train.h"
using namespace std;
#define int long long
#define all(x) (x).begin(), (x).end()
template<template<typename> class Container, typename G>
ostream& operator<<(ostream& os, Container<G> x) {
int f = 0; os << '{'; for (auto &i: x) os << (f++ ? ", " : ""), os << i; os << "}";
return os;
}
void _print() {cerr << "]\n";}
template<typename T, typename... V>
void _print(T t, V... v) {cerr << t; if (sizeof...(v)) cerr <<", "; _print(v...);}
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif
#define pii pair<int, int>
#define f first
#define s second
const int INF=1e18;
struct path{
int a,b,u,v,c,inx;//u->v
path(){inx=0;};
bool operator<(path other){
return b>other.b;
}
};
struct wavelet{
int tl,tr;wavelet *l,*r;vector<int> b;
wavelet(){}
wavelet(int *from,int *to,int x,int y){
tl=x,tr=y;
if(tl==tr or from>=to)return;
int tm=(tl+tr)>>1;
auto f=[tm](int x){return x<=tm;};
b.reserve(to-from+1);
b.push_back(0);
for(auto it=from;it!=to;it++){
b.push_back(b.back()+f(*it));
}
auto pivot=stable_partition(from,to,f);
l=new wavelet(from,pivot,tl,tm);
r=new wavelet(pivot,to,tm+1,tr);
}
int LTE(int l,int r,int k){
if(l>r or k<tl)return 0;
if(tr<=k)return r-l+1;
int lb=b[l-1],rb=b[r];
return this->l->LTE(lb+1ll,rb,k)+this->r->LTE(l-lb,r-rb,k);
}
~wavelet(){
delete l;delete r;
}
};
// need range inside queries in log, so we use pseg or merge sort tree
template<int sz>
struct interval{
vector<pii> v;
wavelet *t;
int a[sz];
void init(){
v.clear();
delete t;
}
void add(int l,int r){
v.emplace_back(l,r);
}
void process(){
sort(all(v));
for(int i=0;i<v.size();i++)a[i]=v[i].s;
t=new wavelet(a,a+v.size(),0,sz);
}
int query(int l,int r){
int inx=lower_bound(all(v),make_pair(l,0ll))-v.begin();int inx2=upper_bound(all(v),make_pair(r,INF))-v.begin()-1;
int ans=t->LTE(inx+1,inx2+1,r);
//int ans=0;for(int i=inx;i<=inx2;i++)ans+=(v[i].s<=r);
return ans;
}
};
interval<1<<20> ds;
template<typename T>
struct lct {
// queries are increasing
int tl,tr;lct<T> *l,*r; T f;
lct(){
init();
}
lct(int a,int b){
init(a,b);
}
// changing r changes the answer wtf
void init(int l=0,int r=1<<20){ // increasing r makes it bigger
tl=l;tr=r;this->l=NULL;this->r=NULL;f={INF,0ll,INF};
}
void add(T l){
int tm=(tl+tr)>>1;
if(make_pair(f.get(tm),f.b)>make_pair(l.get(tm),l.b))swap(l,f);
if(f.get(tl)<=l.get(tl) and f.get(tr)<=l.get(tr))return;
if(tl==tr)return;
if(f.get(tl)>l.get(tl)){
if(!this->l)this->l=new lct(tl,tm);
this->l->add(f);
}else{// if(f.get(tr)>l.get(tr)){
if(!r)r=new lct(tm+1ll,tr);
r->add(f);
}
}
int query(int x){
int tm=(tl+tr)>>1;
int ans=f.get(x);
if(tl==tr)return ans;
if(x<=tm and l){
ans=min(ans,l->query(x));
}else if(r){
ans=min(ans,r->query(x));
}
return ans;
}
};
/*
template<typename T>
struct lct {
// queries are increasing
vector<T> v;
void init(){
v.clear();
}
void add(T l){
v.push_back(l);
}
int query(int x){
int ans=1e18;
for(auto i:v)ans=min(ans,i.get(x));
return ans;
}
};*/
struct F{
int c,m,b;
int get(int x){
//if(c>=INF)return c;
//if(x<=b)return c;
return c+m*(ds.query(b+1ll,x));
}
const bool operator<(F other)const {
return b>other.b;
}
};
priority_queue<F> ins[100005];
lct<F> cht[100005];
int solve(int32_t n,int32_t m,int32_t w,vector<int32_t>t,vector<int32_t>_x,vector<int32_t>_y,vector<int32_t>_a,vector<int32_t>_b,vector<int32_t>_c,vector<int32_t>l,vector<int32_t>r){
for(int i=0;i<n;i++){
while(ins[i].size())ins[i].pop();
cht[i].init();
}
ds.init();
vector<path> paths(m);
vector<int> cmp={-1};
for(int i=0;i<m;i++){
paths[i].u=_x[i];paths[i].v=_y[i];paths[i].a=_a[i];paths[i].b=_b[i];paths[i].c=_c[i];
cmp.push_back(_a[i]);cmp.push_back(_b[i]);
}
for(int i=0;i<w;i++){
cmp.push_back(l[i]);cmp.push_back(r[i]);
}
sort(all(cmp));cmp.resize(unique(all(cmp))-cmp.begin());
for(int i=0;i<m;i++){
paths[i].a=lower_bound(all(cmp),paths[i].a)-cmp.begin();
paths[i].b=lower_bound(all(cmp),paths[i].b)-cmp.begin();
}
for(int i=0;i<w;i++){
l[i]=lower_bound(all(cmp),l[i])-cmp.begin();
r[i]=lower_bound(all(cmp),r[i])-cmp.begin();
ds.add(l[i],r[i]);
}
ds.process();
sort(all(paths),[&](path a,path b){
return a.a<b.a;
});
for(int i=0;i<m;i++)paths[i].inx=i;
// need to put a queue of paths just processed to insert ordered by b value
cht[0].add(F{0,t[0],-1});
for(path i:paths){
// 1. update i.u until we get to i.a
while(ins[i.u].size() and ins[i.u].top().b<=i.a){
cht[i.u].add(ins[i.u].top());ins[i.u].pop();
}
// 2. query cht[i.u] for our i.a-1 value
int v=cht[i.u].query(i.a-1ll)+i.c;
v=min(INF,v);
dbg(i.u,i.v,i.a,i.b,v);
F ne;ne.c=v;ne.m=t[i.v];ne.b=i.b;
// 3. insert the func that we make into
ins[i.v].push(ne);
}
while(ins[n-1].size()){
cht[n-1].add(ins[n-1].top());ins[n-1].pop();
}
int ans=cht[n-1].query(1<<20);
if(ans>=INF)ans=-1;
return ans;
}
