#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const ll inf = 1e18;
const int A = 1e9;
ll 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<pii> d;
for (int i = 0; i < m; i++){
d.pb({b[i], i});
}
sort(d.begin(), d.end());
vector<int> na(m), nb(m), nc(m), nx(m), ny(m);
for (int i = 0; i < m; i++){
int j = d[i].ss;
na[i] = a[j];
nb[i] = b[j];
nc[i] = c[j];
nx[i] = x[j];
ny[i] = y[j];
}
a = na; b = nb; c = nc; x = nx; y = ny;
vector<int> g[n + 1];
for (int i = 0; i < m; i++){
x[i]++; y[i]++;
g[y[i]].pb(i);
}
t.insert(t.begin(), 0);
vector<pii> all;
for (int i = 0; i < w; i++){
all.pb({l[i], r[i]});
}
auto cmp1 = [&](pii x, pii y){
return x.ss < y.ss;
};
sort(all.begin(), all.end(), cmp1);
auto f = [&](int l, int r){
int out = 0;
for (auto [x, y]: all){
out += (l < x && y < r);
}
return out;
};
vector<pii> ed;
for (int i = 0; i < m; i++){
ed.pb({a[i], i});
}
sort(ed.begin(), ed.end());
vector<ll> dp(m);
vector<int> s(n + 1);
auto G = [&](int l, int r, ll k){
if (k <= 0) return 0;
int cc = 0;
for (auto [x, y]: all){
cc += (l < x && x <= r);
if (cc == k) return y;
}
return A;
};
set<int> st[n + 1];
priority_queue<pii, vector<pii>, greater<pii>> pq[n + 1];
ll out = inf;
for (auto [B, i]: ed){
int v = x[i];
while (s[v] < g[v].size() && b[g[v][s[v]]] <= a[i]){
int x = g[v][s[v]];
if (st[v].empty()){
st[v].insert(x);
s[v]++;
continue;
}
int y = *prev(st[v].end());
pq[v].push({G(b[y], b[x], ceil(1.0 * (dp[x] - dp[y]) / t[v])), y});
st[v].insert(x); s[v]++;
}
while (!pq[v].empty() && pq[v].top().ff < a[i]){
auto [x, y] = pq[v].top(); pq[v].pop();
if (st[v].find(y) == st[v].end()) continue;
auto it = st[v].find(y);
if (it != prev(st[v].end()) && it != st[v].begin()){
int y1 = *next(it), y2 = *prev(it);
pq[v].push({G(b[y2], b[y1], ceil(1.0 * (dp[y1] - dp[y2]) / t[v])), y2});
}
st[v].erase(y);
}
ll mn = inf;
for (int x: st[v]){
mn = min(mn, dp[x] + 1LL * t[v] * f(b[x], a[i]));
}
if (x[i] == 1) mn = min(mn, 1LL * t[v] * f(0, a[i]));
dp[i] = mn + c[i];
if (y[i] == n){
out = min(out, dp[i] + 1LL * t[n] * f(b[i], A + 1));
}
}
if (out == inf) return -1;
return out;
}
