#include "train.h"
#include <bits/stdc++.h>
#define maxn 100005
#define fi first
#define se second
#define int64_t long long
using namespace std;
using ii = pair<int, int>;
using il = pair<int, int64_t>;
using li = pair<int64_t, int>;
int n, m, w, t[maxn], root[maxn];
int A[maxn], B[maxn], n1 = 0, n2 = 0;
int64_t ans = LLONG_MAX/2;
namespace pst {
int nt = 0, it[22*maxn], L[22*maxn], R[22*maxn];
int build(int lo = 1, int hi = n2) {
if (lo == hi) return ++nt;
int cur = ++nt, mid = (lo + hi) >> 1;
L[cur] = build(lo, mid);
R[cur] = build(mid+1, hi);
return nt;
}
int upd(int u, int d, int oldver, int lo = 1, int hi = n2) {
if (lo == hi) {
it[++nt] = it[oldver] + 1;
return nt;
}
int cur = ++nt, mid = (lo + hi) >> 1;
if (u <= mid) {
L[cur] = upd(u, d, L[oldver], lo, mid);
R[cur] = R[oldver];
} else {
L[cur] = L[oldver];
R[cur] = upd(u, d, R[oldver], mid+1, hi);
}
it[cur] = it[L[cur]] + it[R[cur]];
return cur;
}
int get(int u, int v, int r, int lo = 1, int hi = n2) {
if (u <= lo && hi <= v) return it[r];
int mid = (lo + hi) >> 1;
return (u <= mid ? get(u, v, L[r], lo, mid) : 0)
+ (v > mid ? get(u, v, R[r], mid+1, hi) : 0);
}
int bfind(int k, int rootOne, int rootTwo, int lo = 1, int hi = n2) {
if (lo == hi) return lo;
int mid = (lo + hi) >> 1, trai = it[rootTwo]-it[rootOne];
if (k > trai) return bfind(k-trai, R[rootOne], R[rootTwo], mid+1, hi);
return bfind(k, L[rootOne], L[rootTwo], lo, mid);
}
}
struct edge {
int x, y, a, b, c;
bool operator < (const edge &other) const {
return b < other.b;
}
} edges[maxn];
ii meals[maxn];
int64_t dp[maxn];
deque<int> q[maxn];
int64_t mainProgram() {
sort(edges + 1, edges + m + 1);
for (int i = 1; i <= w; i++) {
A[++n1] = meals[i].fi;
B[++n2] = meals[i].se;
}
sort(A + 1, A + n1 + 1);
sort(B + 1, B + n2 + 1);
n1 = unique(A + 1, A + n1 + 1) - A - 1;
n2 = unique(B + 1, B + n2 + 1) - B - 1;
sort(meals + 1, meals + w + 1, [&](const ii &a, const ii &b) {return a.fi < b.fi;});
root[0] = pst::build();
for (int i = 1, it = 1; i <= n1; i++) {
root[i] = root[i-1];
while (it <= w && meals[it].fi == A[i]) {
int p = lower_bound(B + 1, B + n2 + 1, meals[it].se) - B;
root[i] = pst::upd(p, 1, root[i]);
++it;
}
}
for (int i = 1; i <= m; i++) dp[i] = LLONG_MAX/2;
for (int i = 1; i <= m; i++) {
if (edges[i].x == 1) {
int p = lower_bound(B + 1, B + n2 + 1, edges[i].a) - B - 1;
dp[i] = edges[i].c + 1LL * t[edges[i].x] * (1 <= p ? pst::get(1, p, root[n1]) : 0);
}
deque<int> &cur = q[edges[i].x];
function<bool(int, int)> better = [&](int x_1, int x_2) {
if (dp[x_1] <= dp[x_2]) return true;
int64_t C = dp[x_1] - dp[x_2];
int64_t needed = (C-1) / t[edges[i].x] + 1;
int p = upper_bound(A + 1, A + n1 + 1, edges[x_2].b) - A - 1, q = upper_bound(A + 1, A + n1 + 1, edges[x_1].b) - A - 1;
if (p == q || p > q) return false;
if (pst::it[root[q]] - pst::it[root[p]] < needed) return false;
int pos = pst::bfind(needed, root[p], root[q]),
LAST = B[pos]+1;
return LAST <= edges[i].a;
};
if (!cur.empty()) {
while (cur.size() > 1 && edges[cur[1]].b <= edges[i].a && better(cur[1], cur[0])) cur.pop_front();
int cr = cur[0];
int p = upper_bound(A + 1, A + n1 + 1, edges[cr].b) - A - 1,
q = upper_bound(A + 1, A + n1 + 1, edges[i].a) - A - 1,
z = lower_bound(B + 1, B + n2 + 1, edges[i].a) - B - 1;
dp[i] = min(dp[i], dp[cr] + 1LL * t[edges[i].x] * (1 <= z ? (pst::get(1, z, root[q]) - pst::get(1, z, root[p])) : 0));
}
q[edges[i].y].push_back(i);
}
for (int i = 1; i <= m; i++)
if (edges[i].y == n) {
int p = upper_bound(A + 1, A + n1 + 1, edges[i].b) - A - 1;
int h = pst::get(1, n2, root[n1]) - pst::get(1, n2, root[p]);
ans = min(ans, dp[i] + 1LL * t[edges[i].y] * h);
}
return ans >= LLONG_MAX/2 ? -1 : ans;
}
long long 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) {
n = N; m = M; w = W;
for (int i = 1; i <= n; i++) t[i] = T[i-1];
for (int i = 1; i <= m; i++) edges[i] = edge{X[i-1]+1, Y[i-1]+1, A[i-1], B[i-1], C[i-1]};
for (int i = 1; i <= w; i++) meals[i] = ii{L[i-1], R[i-1]};
return mainProgram();
}
/*
3 3 1
20 30 40
0 1 1 15 10
1 2 20 30 5
0 2 18 40 40
16 19
40
*/
/*
3 5 6
30 38 33
0 2 12 16 38
1 0 48 50 6
0 1 26 28 23
0 2 6 7 94
1 2 49 54 50
32 36
14 14
42 45
37 40
2 5
4 5
197
*/
