#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#include "train.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+100, S=4000;
const ll inf=1e18;
struct DS{
int lazy[N], add[N];
void update(int x){
int id=x>>9;
for (int i=0; i<id; ++i) ++lazy[i];
for (int i=id<<9; i<=x; ++i) ++add[i];
}
int get(int x){
return lazy[x>>9]+add[x];
}
} ds;
struct SegmentTree{
int n;
vector<ll> val, lazy;
void init(int _n, ll x=0){
n=_n;
lazy.assign(4*n, 0);
val.assign(4*n, x);
}
void apply(int k, ll x){
val[k]+=x;
lazy[k]+=x;
}
void push(int k){
if (lazy[k]){
apply(k<<1, lazy[k]);
apply(k<<1|1, lazy[k]);
lazy[k]=0;
}
}
void update(int k, int l, int r, int L, int R, ll x){
if (r<L || R<l) return;
if (L<=l && r<=R){
apply(k, x);
return;
}
push(k);
int mid=(l+r)>>1;
update(k<<1, l, mid, L, R, x);
update(k<<1|1, mid+1, r, L, R, x);
val[k]=min(val[k<<1], val[k<<1|1]);
}
ll get(int k, int l, int r, int L, int R){
if (r<L || R<l) return inf;
if (L<=l && r<=R) return val[k];
push(k);
int mid=(l+r)>>1;
return min(get(k<<1, l, mid, L, R), get(k<<1|1, mid+1, r, L, R));
}
};
struct State{
int u, time;
State (int _u=0, int _time=0){
u=_u, time=_time;
}
bool operator<(const State &a){
return tie(u, time)<tie(a.u, a.time);
}
bool operator==(const State &a){
return tie(u, time)==tie(a.u, a.time);
}
};
vector<State> vs;
vector<int> vt;
int n, m, cost[N], heavy[N];
vector<pair<int, int>> g[N];
vector<int> vv[N], qq[N];
ll f[N], ff[N];
vector<int> add[N];
int id[N];
SegmentTree st[N/S+10];
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) {
n=N_, m=M;
for (int i=0; i<n; ++i) cost[i]=T[i];
vt.push_back(-1);
vt.push_back(0); vt.push_back(2e9);
for (int i=0; i<m; ++i) vt.push_back(A[i]), vt.push_back(B[i]);
sort(vt.begin(), vt.end()); vt.resize(unique(vt.begin(), vt.end())-vt.begin());
for (int i=0; i<W; ++i){
L[i]=lower_bound(vt.begin(), vt.end(), L[i])-vt.begin();
R[i]=upper_bound(vt.begin(), vt.end(), R[i])-vt.begin()-1;
}
for (int i=0; i<m; ++i){
A[i]=lower_bound(vt.begin(), vt.end(), A[i])-vt.begin();
B[i]=lower_bound(vt.begin(), vt.end(), B[i])-vt.begin();
vs.emplace_back(X[i], A[i]);
vs.emplace_back(Y[i], B[i]);
}
vs.emplace_back(0, 1);
vs.emplace_back(n-1, (int)vt.size()-1);
sort(vs.begin(), vs.end()); vs.resize(unique(vs.begin(), vs.end())-vs.begin());
for (int i=0; i<m; ++i){
int i1=lower_bound(vs.begin(), vs.end(), State(X[i], A[i]))-vs.begin();
int i2=lower_bound(vs.begin(), vs.end(), State(Y[i], B[i]))-vs.begin();
g[i2].emplace_back(i1, C[i]);
}
for (int i=0; i<(int)vs.size(); ++i) vv[vs[i].u].push_back(i), qq[vs[i].time].push_back(i);
for (int i=0; i<n; ++i) f[i]=inf;
vector<int> vh;
for (int i=0; i<n; ++i) if ((int)vv[i].size()>S){
heavy[i]=1;
st[vh.size()].init((int)vt.size(), inf);
id[i]=vh.size();
vh.push_back(i);
}
for (int i=0; i<W; ++i) add[R[i]+1].push_back(L[i]-1);
for (int i=0; i<N; ++i) f[i]=ff[i]=inf;
ff[0]=0;
for (int i=0; i<(int)vt.size(); ++i){
for (int j:add[i]){
for (int k=0; k<(int)vh.size(); ++k) st[k].update(1, 1, st[k].n, 1, j, cost[vh[k]]);
ds.update(j);
}
for (int j:qq[i]){
for (auto &e:g[j]){
ff[j]=min(ff[j], f[e.first]+e.second);
}
}
for (int j:qq[i]){
int u=vs[j].u;
if (heavy[u]){
st[id[u]].update(1, 1, st[id[u]].n, vs[j].time, vs[j].time, ff[j]-inf);
}
}
for (int j:qq[i]){
int u=vs[j].u;
if (heavy[u]){
f[j]=min(f[j], st[id[u]].get(1, 1, st[id[u]].n, 1, vs[j].time));
}else{
for (int k:vv[u]) if (vs[k].time<=vs[j].time){
f[j]=min(f[j], ff[k]+1ll*ds.get(vs[k].time)*cost[u]);
}
}
}
}
ll ans=f[(int)vs.size()-1];
if (ans==inf) ans=-1;
return ans;
}
