#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#include "train.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using arl2 = array<ll, 2>;
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
constexpr int mxN = 100005;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
struct Node {
int val;
Node *lft, *rht;
Node(int v) : val(v), lft(nullptr), rht(nullptr) {}
Node(Node *l, Node *r) : val(l->val + r->val), lft(l), rht(r) {}
Node(Node *n) : val(n->val), lft(n->lft), rht(n->rht) {}
};
vt<int> cmp_l, cmp_r;
Node *sts[mxN<<1];
Node *build(int tl = 0, int tr = size(cmp_r)-1) {
if (tl == tr)
return new Node(0);
int tm = tl + tr >> 1;
return new Node(build(tl, tm), build(tm+1, tr));
}
Node *update(Node *n, int p, int v, int tl = 0, int tr = size(cmp_r)-1) {
if (tl == tr)
return new Node(n->val + v);
int tm = tl + tr >> 1;
if (p <= tm)
return new Node(update(n->lft, p, v, tl, tm), n->rht);
return new Node(n->lft, update(n->rht, p, v, tm+1, tr));
}
int query(Node *n, int ql, int qr, int tl = 0, int tr = size(cmp_r)-1) {
if (tl > qr || tr < ql)
return 0;
if (ql <= tl && tr <= qr)
return n->val;
int tm = tl + tr >> 1;
return query(n->lft, ql, qr, tl, tm) + query(n->rht, ql, qr, tm+1, tr);
}
struct Line {
int l, m;
ll c;
ll eval(int x) {
return 1ll * m * query(sts[l], 0, x) + c;
}
};
struct Lichao {
Line line;
Lichao *lft, *rht;
void update(Line new_line, int tl = 0, int tr = size(cmp_r)-1) {
int tm = tl + tr >> 1;
if (make_pair(new_line.eval(tm), -new_line.l) < make_pair(line.eval(tm), -line.l))
swap(new_line, line);
if (tl == tr)
return;
if (new_line.eval(tl) < line.eval(tl)) {
if (!lft) {
lft = new Lichao();
lft->line = {0, 0, LLONG_MAX};
lft->lft = lft->rht = nullptr;
}
lft->update(new_line, tl, tm);
} else {
if (!rht) {
rht = new Lichao();
rht->line = {0, 0, LLONG_MAX};
rht->lft = rht->rht = nullptr;
}
rht->update(new_line, tm+1, tr);
}
}
ll query(int x, int tl = 0, int tr = size(cmp_r)-1) {
ll ret = line.eval(x);
int tm = tl + tr >> 1;
if (x <= tm)
return min(ret, lft ? lft->query(x, tl, tm) : ret);
return min(ret, rht ? rht->query(x, tm+1, tr) : ret);
}
};
vt<ari2> adj[mxN*2];
vt<int> ins[mxN*2];
int node[mxN*2], times[mxN*2], ord[mxN*2];
Lichao *lcts[mxN];
ll dp[mxN*2];
ll solve(int N, int M, int W, vt<int> T, vt<int> X, vt<int> Y,
vt<int> A, vt<int> B, vt<int> C, vt<int> L, vt<int> R) {
map<ari2, int> ind;
ind[{0, 0}] = 0;
FOR(i, 0, M-1) {
int x = X[i], y = Y[i], a = A[i], b = B[i];
if (ind.find({x, a}) == end(ind))
ind[{x, a}] = size(ind);
if (ind.find({y, b}) == end(ind))
ind[{y, b}] = size(ind);
}
const int K = size(ind);
FOR(i, 0, M-1) {
int a = ind[{X[i], A[i]}];
int b = ind[{Y[i], B[i]}];
node[a] = X[i], times[a] = A[i];
node[b] = Y[i], times[b] = B[i];
adj[a].push_back({b, C[i]});
}
{
cmp_l.push_back(0);
cmp_r.push_back(0);
FOR(i, 0, W-1) {
cmp_l.push_back(L[i]);
cmp_r.push_back(R[i]);
}
sort(all(cmp_l));
cmp_l.erase(unique(all(cmp_l)), end(cmp_l));
sort(all(cmp_r));
cmp_r.erase(unique(all(cmp_r)), end(cmp_r));
FOR(i, 0, W-1) {
ins[lower_bound(all(cmp_l), L[i]) - begin(cmp_l)].push_back(lower_bound(all(cmp_r), R[i]) - begin(cmp_r));
}
sts[size(cmp_l)] = build();
ROF(i, size(cmp_l)-1, 0) {
sts[i] = new Node(sts[i+1]);
for (int j : ins[i])
sts[i] = update(sts[i], j, 1);
}
}
iota(ord, ord+K, 0);
sort(ord, ord+K, [&](const int &a, const int &b) {
return times[a] < times[b];
});
memset(dp, 0x3f, K<<3);
FOR(i, 0, N-1) {
lcts[i] = new Lichao();
lcts[i]->line = {0, 0, LLONG_MAX};
lcts[i]->lft = lcts[i]->rht = nullptr;
}
dp[0] = 0;
ll ans = INF;
for (int i : ord) {
ll go = lcts[node[i]]->query(lower_bound(all(cmp_r), times[i]) - begin(cmp_r) - 1);
if (min(go, dp[i]) < INF)
for (auto [j, v] : adj[i])
dp[j] = min(dp[j], min(go, dp[i]) + v);
int j = upper_bound(all(cmp_l), times[i]) - begin(cmp_l);
if (dp[i] < INF)
lcts[node[i]]->update({j, T[node[i]], dp[i]});
if (node[i] == N-1 && dp[i] < INF)
ans = min(ans, dp[i] + 1ll * T[node[i]] * (j < size(cmp_l) ? sts[j]->val : 0));
}
return ans < INF ? ans : -1;
}
