#include "train.h"
#include <bits/stdc++.h>
using namespace std;
//#include "stub.cpp"
typedef long long ll;
const int MAXN = 5e5 + 25;
const int B = 800;
const int B2 = 400;
struct SQRT {
int f[MAXN], g[MAXN / B2 + 2];
void add (int x) {
while (x % B2 != 0) {
f[x]++;
x++;
}
x /= B2;
while (x <= MAXN / B2 + 1) {
g[x]++;
x++;
}
}
int get (int x) {
if (x < 0) return 0;
return f[x] + g[x / B2];
}
} ds;
vector <int> cc;
int find (int x) {
return lower_bound(cc.begin(), cc.end(), x) - cc.begin();
}
#define mid ((l + r) >> 1)
#define tl (node << 1)
#define tr (node << 1 | 1)
const ll inf = 1e18;
struct SegmentTree {
vector <ll> tree, lazy;
void init (int sze) {
tree.resize(4 * sze);
lazy.resize(4 * sze);
for (auto &i : tree) {
i = inf;
}
}
void set (int l, int r, int a, ll b, int node) {
if (l == r) {
tree[node] = min(tree[node], b);
return;
}
if (a <= mid) set(l, mid, a, b, tl);
else set(mid + 1, r, a, b, tr);
tree[node] = min(tree[tl] + lazy[tl], tree[tr] + lazy[tr]);
}
void update (int l, int r, int a, int b, int c, int node) {
if (l > b || r < a) return;
if (l >= a && r <= b) {
lazy[node] += c;
return;
}
update(l, mid, a, b, c, tl); update(mid + 1, r, a, b, c, tr);
tree[node] = min(tree[tl] + lazy[tl], tree[tr] + lazy[tr]);
}
ll get (int l, int r, int a, int b, int node) {
if (l > b || r < a) return inf;
if (l >= a && r <= b) return tree[node] + lazy[node];
return min(get(l, mid, a, b, tl), get(mid + 1, r, a, b, tr)) + lazy[node];
}
} cur[MAXN / B + 2];
int ind[MAXN];
vector <int> ii[MAXN];
vector <int> heavy;
vector <int> ee1[MAXN], ee2[MAXN], ee3[MAXN];
ll dp[MAXN];
vector <int> indices[MAXN];
int ff (int x, int y) {
return lower_bound(ii[x].begin(), ii[x].end(), y) - ii[x].begin();
}
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 (int i = 0; i < w; i++) {
cc.push_back(l[i]);
cc.push_back(r[i]);
}
for (int i = 0; i < m; i++) {
cc.push_back(a[i]);
cc.push_back(b[i]);
}
sort(cc.begin(), cc.end());
cc.resize(unique(cc.begin(), cc.end()) - cc.begin());
for (int i = 0; i < w; i++) {
l[i] = find(l[i]);
r[i] = find(r[i]);
}
for (int i = 0; i < m; i++) {
a[i] = find(a[i]);
b[i] = find(b[i]);
ii[x[i]].push_back(a[i]);
indices[x[i]].push_back(i);
}
for (int i = 0; i < n; i++) {
ii[i].push_back((int)cc.size() + 2);
sort(ii[i].begin(), ii[i].end());
ii[i].resize(unique(ii[i].begin(), ii[i].end()) - ii[i].begin());
if ((int)ii[i].size() > B) {
ind[i] = heavy.size();
heavy.push_back(i);
cur[ind[i]].init((int)ii[i].size());
if (i == n - 1) {
for (int j = 0; j < (int)ii[i].size(); j++) {
cur[ind[i]].set(0, (int)ii[i].size() - 1, j, 0, 1);
}
}
}
}
for (int i = 0; i < m; i++) {
ee1[b[i]].push_back(i);
ee2[a[i]].push_back(i);
}
for (int i = 0; i < w; i++) {
ee3[l[i]].push_back(i);
}
for (int i = (int)cc.size() - 1; i >= 0; i--) {
for (auto j : ee2[i]) {
if ((int)ii[x[j]].size() > B) {
cur[ind[x[j]]].set(0, (int)ii[x[j]].size() - 1, ff(x[j], i), dp[j], 1);
}
}
for (auto j : ee1[i]) {
if (y[j] == n - 1) {
dp[j] = (ll)c[j] + (ll)t[n - 1] * (ll)ds.get(MAXN - 1);
continue;
}
if ((int)ii[y[j]].size() > B) {
dp[j] = c[j] + cur[ind[y[j]]].get(0, (int)ii[y[j]].size() - 1, ff(y[j], b[j]), (int)ii[y[j]].size() - 1, 1);;
} else {
dp[j] = inf;
for (auto k : indices[y[j]]) {
if (b[j] <= a[k]) {
dp[j] = min(dp[j], c[j] + dp[k] + (ll)t[y[j]] * (ll)ds.get(a[k]));
}
}
}
}
for (auto j : ee3[i]) {
ds.add(r[j] + 1);
for (auto k : heavy) {
cur[ind[k]].update(0, (int)ii[k].size() - 1, ff(k, r[j] + 1), (int)ii[k].size() - 1, t[k], 1);
}
}
}
ll ret = inf;
for (int i = 0; i < m; i++) {
if (x[i] == 0) {
ret = min(ret, dp[i] + (ll)t[0] * (ll)ds.get(a[i]));
}
}
if (ret == inf) ret = -1;
return ret;
}
