#include "train.h"
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(ll i=0;i<(n);++i)
#define repr(i,n) for(ll i=(n)-1;i>=0;--i)
#define repa(i,m,n) for(ll i=(m);i<(n);++i)
#define repra(i,m,n) for(ll i=(n)-1;i>=(m);--i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
constexpr ll INF=1LL<<60;
struct ll2{ll a,b;friend auto operator<=>(ll2,ll2)=default;};
struct ll3{ll a,b,c;friend auto operator<=>(ll3,ll3)=default;};
struct ll4{ll a,b,c,d;friend auto operator<=>(ll4,ll4)=default;};
struct ll5{ll a,b,c,d,e;friend auto operator<=>(ll5,ll5)=default;};
template<typename T>
ostream& operator<<(ostream& os,vector<T> A){
os<<'(';
for(T a:A)os<<a<<' ';
os<<')';
return os;
}
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<ll2> S(W),S2(W);
rep(i,W){
S[i]={L[i],R[i]};
S2[i]={R[i],L[i]};
}
sort(all(S));
sort(all(S2));
multiset<ll4> ev;
rep(i,M)ev.emplace(A[i],3,X[i],i);
vector<multiset<ll>> ar1(N,{INF});
vector<ll> ar2(N,INF);
ar2[0]=0;
while(ev.size()){
auto[a,t,x,i]=*ev.begin();
ev.erase(ev.begin());
//cout<<a<<' '<<t<<' '<<x<<' '<<i<<endl;
if(t==3){
ll ko=lower_bound(all(S2),ll2{a,-INF})-S2.begin();
ll cs=min(*ar1[x].begin(),ar2[x]+ko*T[x]);
ll u=lower_bound(all(S),ll2{B[i],INF})-S.begin();
if(u&&S[u-1].a<=B[i]&&B[i]<=S[u-1].b){
ev.emplace(B[i],0,Y[i],cs+C[i]);
ev.emplace(S[u-1].b+1,1,Y[i],cs+C[i]);
ev.emplace(S[u-1].b+1,2,Y[i],cs+C[i]-T[Y[i]]*u);
}else ev.emplace(B[i],2,Y[i],cs+C[i]-T[Y[i]]*u);
}else if(t==0)ar1[x].insert(i);
else if(t==1)ar1[x].erase(ar1[x].find(i));
else ar2[x]=min(ar2[x],i);
}
//cout<<ar2<<endl;
ll ans=min(*ar1[N-1].begin(),ar2[N-1]+W*T[N-1]);
if(ans>1000000000000000LL)return -1;
return ans;
}
