#include "train.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mxN = 1e5+5;
vector <tuple <int, int, int, int, int>> adj[mxN];
vector <ll> dis[mxN];
vector <int> CC;
struct PST {
struct {
int val, l, r;
} pool[mxN<<5];
int it = 0, seg[mxN];
int nw(int x) {
pool[++it] = {x, 0, 0};
return it;
}
int nw(int l, int r) {
pool[++it] = {pool[l].val + pool[r].val, l, r};
return it;
}
int build(int l, int r) {
if (l == r) return nw(0);
else {
int m = l + (r-l)/2;
return nw(build(l, m), build(m+1, r));
}
}
int upd(int l, int r, int idx, int x, int u) {
if (l == r) return nw(pool[u].val + x);
else {
int m = l + (r-l)/2;
if (m >= idx) return nw(upd(l, m, idx, x, pool[u].l), pool[u].r);
else return nw(pool[u].l, upd(m+1, r, idx, x, pool[u].r));
}
}
int qr(int l, int r, int x, int y, int u) {
if (y < x) return 0;
if (x <= l && r <= y) return pool[u].val;
else {
int m = l + (r-l)/2, cnt = 0;
if (m >= x) cnt += qr(l, m, x, y, pool[u].l);
if (m+1 <= y) cnt += qr(m+1, r, x, y, pool[u].r);
return cnt;
}
}
} Tr;
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) {
for (auto &e : L) CC.emplace_back(e);
for (auto &e : R) CC.emplace_back(e);
for (auto &e : A) CC.emplace_back(e);
for (auto &e : B) CC.emplace_back(e);
CC.emplace_back(0);
CC.emplace_back(INT_MAX);
sort(CC.begin(), CC.end());
CC.resize(unique(CC.begin(), CC.end()) - CC.begin());
auto fi = [&] (int x) {
return upper_bound(CC.begin(), CC.end(), x) - CC.begin();
};
for (auto &e : L) e = fi(e);
for (auto &e : R) e = fi(e);
for (auto &e : A) e = fi(e);
for (auto &e : B) e = fi(e);
dis[0].emplace_back(0);
for (int i = 0; i < M; i++) {
adj[X[i]].emplace_back(Y[i], C[i], A[i], B[i], (int) dis[Y[i]].size());
dis[Y[i]].emplace_back(LLONG_MAX);
}
adj[N-1].emplace_back(N, 0, fi(INT_MAX), fi(INT_MAX), (int) dis[N].size());
dis[N].emplace_back(LLONG_MAX);
vector <pair <int, int>> Q;
for (int i = 0; i < W; i++) Q.emplace_back(R[i], L[i]);
sort(Q.begin(), Q.end());
int sz = fi(INT_MAX);
Tr.seg[0] = Tr.build(1, sz);
for (int i = 0; i < W; i++) {
// cout << i+1 << ' ' << Q[i].second << ' ' << Q[i].first << '\n';
Tr.seg[i+1] = Tr.upd(1, sz, Q[i].second, 1, Tr.seg[i]);
}
dis[0][0] = 0;
priority_queue <tuple <ll, int, int, int>> q;
q.emplace(0, 0, 0, fi(0));
auto cnt = [&] (int x, int y) {
// cout << "FI " << x << ' ' << y << '\n';
int idx = upper_bound(Q.begin(), Q.end(), make_pair(y, INT_MAX)) - Q.begin();
// cout << idx << ' ' << x << '\n';
// cout << Tr.qr(1, sz, x, sz, Tr.seg[idx]) << '\n';
return Tr.qr(1, sz, x, sz, Tr.seg[idx]);
// ll cc = 0;
// for (auto &[r, l] : Q) cc += (x <= l && r <= y);
// return cc;
};
while (q.size()) {
auto [w, u, id, t] = q.top(); q.pop();
w = -w;
if (w != dis[u][id]) continue;
// cout << u << ' ' << CC[t-1] << ' ' << w << '\n';
if (u == N) return w;
for (auto [v, dw, x, y, ii] : adj[u]) {
if (x < t) continue;
ll nw = w + dw + (ll) T[u] * cnt(t+1, x-1);
if (dis[v][ii] > nw) q.emplace(-(dis[v][ii] = nw), v, ii, y);
}
}
return -1;
}
