#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;
struct PST{
struct node{
node *l, *r;
int k;
node(int x){
l = r = 0;
k = x;
}
node(node *ls, node *rs){
l = ls; r = rs;
k = 0;
if (l) k += l -> k;
if (r) k += r -> k;
}
};
vector<node*> root;
vector<int> f = {0}, pp;
int n, m, cc;
vector<int> :: iterator it;
PST(int ns, int ms, vector<int> ps){
n = ns; m = ms; pp = ps;
root.resize(m + 1);
root[0] = build(1, n);
cc = 0;
}
node* build(int tl, int tr){
if (tl == tr) return new node(0);
int tm = (tl + tr) / 2;
return new node(build(tl, tm), build(tm + 1, tr));
}
node* upd(node *v, int tl, int tr, int x){
if (tl == tr) return new node(v -> k + 1);
int tm = (tl + tr) / 2;
if (x <= tm){
return new node(upd(v -> l, tl, tm, x), v -> r);
}
else {
return new node(v -> l, upd(v -> r, tm + 1, tr, x));
}
}
void upd(int x, int y){
f.pb(y);
it = upper_bound(pp.begin() + 1, pp.end(), x); it--;
x = (int) (it - pp.begin());
cc++;
root[cc] = upd(root[cc - 1], 1, n, x);
}
int get(node *v, int tl, int tr, int l, int r){
if (l > tr || r < tl) return 0;
if (l <= tl && tr <= r) return v -> k;
int tm = (tl + tr) / 2;
return get(v -> l, tl, tm, l, r) + get(v -> r, tm + 1, tr, l, r);
}
int F(int l, int r){
l++; r--;
if (l > r) return 0;
it = upper_bound(f.begin() + 1, f.end(), r); it--;
r = (int) (it - f.begin());
it = lower_bound(pp.begin() + 1, pp.end(), l);
l = (int) (it - pp.begin());
return get(root[r], 1, n, l, n);
}
int kth(node *vr, node *vl, int tl, int tr, ll k){
if (tl == tr) return pp[tl];
int tm = (tl + tr) / 2, cc = vr -> l -> k - vl -> l -> k;
if (cc >= k) return kth(vr -> l, vl -> l, tl, tm, k);
return kth(vr -> r, vl -> r, tm + 1, tr, k - cc);
}
int G(int l, int r, ll k){
l++;
if (l > r) return A;
it = upper_bound(f.begin() + 1, f.end(), r); it--;
r = (int) (it - f.begin());
it = upper_bound(f.begin() + 1, f.end(), l - 1); it--;
l = (int) (it - f.begin());
if ((root[r] -> k - root[l] -> k) < k) return A;
return kth(root[r], root[l], 1, n, k);
}
};
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);
vector<int> pp = {0};
for (auto [x, y]: all){
pp.pb(x); pp.pb(y);
}
for (int i = 0; i < m; i++){
pp.pb(b[i]);
}
sort(pp.begin(), pp.end());
int N = (int) pp.size();
PST T(N, (int) all.size(), pp);
for (auto [x, y]: all){
T.upd(x, y);
}
auto f = [&](int l, int r){
return T.F(l, r);
};
PST F(N, (int) all.size(), pp);
sort(all.begin(), all.end());
for (auto [x, y]: all){
F.upd(y, x);
}
auto G = [&](int l, int r, ll k){
if (k <= 0) return 0;
return F.G(l, r, k);
};
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);
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;
if (!st[v].empty()){
int x = *st[v].begin();
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;
}
