#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int N = 1e5 + 1;
int n, m, w, cost[N], meal2[N], cnt = 0, cur = 0;
long long dist[N];
set<pair<long long, int>> city[N];
vector<int> g[N];
priority_queue<pair<int, int>> q;
int rt[N], ls[30 * N], rs[30 * N], it[30 * N];
struct Edge {
int x, y, a, b, c;
bool operator<(const Edge &u) const { return a < u.a; }
} e[N];
struct Meal {
int l, r, id;
} meal[N];
bool cmp1(const Meal &x, const Meal &y) { return make_pair(x.r, x.l) < make_pair(y.r, y.l); }
bool cmp2(const Meal &x, const Meal &y) { return x.l < y.l; }
void upd(int i, int old, int l, int r, int p) {
it[i] = it[old] + 1;
if (l == r) return;
int mid = (l + r) >> 1;
if (p <= mid) {
rs[i] = rs[old];
upd(ls[i] = ++cnt, ls[old], l, mid, p);
} else {
ls[i] = ls[old];
upd(rs[i] = ++cnt, rs[old], mid + 1, r, p);
}
}
int query(int i, int l, int r, int u, int v) {
if (!i || l > v || r < u) return 0;
if (u <= l && r <= v) return it[i];
int mid = (l + r) >> 1;
return query(ls[i], l, mid, u, v) + query(rs[i], mid + 1, r, u, v);
}
long long getval(int i) {
long long res = dist[i];
if (cur == 0) return res;
int p = upper_bound(meal2, meal2 + w, e[i].b) - meal2;
long long cnt = cur;
if (p) cnt -= query(rt[p - 1], 0, w - 1, 0, cur - 1);
assert(cnt >= 0);
return res + cnt * cost[e[i].y];
}
int findkth(int i, int j, int l, int r, int k) {
if (l == r) return l;
int mid = (l + r) >> 1, t = it[ls[j]] - it[ls[i]];
if (k <= t) return findkth(ls[i], ls[j], l, mid, k);
return findkth(rs[i], rs[j], mid + 1, r, k - t);
}
int getkth(int l, int r, long long k) {
l = lower_bound(meal2, meal2 + w, l) - meal2;
r = upper_bound(meal2, meal2 + w, r) - meal2;
if (!r || r - l < k) return -1;
return findkth(l ? rt[l - 1] : 0, rt[r - 1], 0, w - 1, k);
}
void calc(int i) {
int v = e[i].y;
int j = prev(city[v].find(make_pair(dist[i], i)))->second;
long long dif = dist[i] - dist[j];
long long k = (dif + cost[v] - 1) / cost[v];
int kth = getkth(e[j].b + 1, e[i].b, k);
if (kth != -1) g[kth].push_back(i), assert(kth >= cur);
}
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 = 0; i < n; i++) cost[i] = T[i];
for (int i = 0; i < m; i++) e[i] = { X[i], Y[i], A[i], B[i], C[i] };
sort(e, e + m);
for (int i = 0; i < w; i++) meal[i] = { L[i], R[i], 0 };
sort(meal, meal + w, cmp1);
for (int i = 0; i < w; i++) meal[i].id = i;
sort(meal, meal + w, cmp2);
for (int i = 0; i < w; i++) {
upd(rt[i] = ++cnt, i ? rt[i - 1] : 0, 0, w - 1, meal[i].id);
meal2[i] = meal[i].l;
}
sort(meal, meal + w, cmp1);
memset(dist, -1, 8 * m);
city[0].insert(make_pair(0, m));
e[m].b = -1;
bool ok = 0;
for (int i = 0; i < m; i++) {
if (i == 250) ok = 1;
while (cur < w && meal[cur].r < e[i].a) {
cur++;
for (int j : g[cur - 1]) {
int v = e[j].y;
auto it = city[v].find(make_pair(dist[j], j));
if (it == city[v].end()) continue;
while (it != city[v].begin() && getval(prev(it)->second) >= getval(j)) city[v].erase(prev(it));
if (it != city[v].begin()) calc(j);
}
}
while (q.size() && -q.top().first <= e[i].a) {
int j = q.top().second;
q.pop();
int v = e[j].y;
while (city[v].size() && getval(city[v].rbegin()->second) >= getval(j)) city[v].erase(--city[v].end());
city[v].insert(make_pair(dist[j], j));
if (city[v].size() > 1) calc(j);
}
int u = e[i].x;
if (city[u].empty()) continue;
dist[i] = getval(city[u].begin()->second) + e[i].c;
q.push(make_pair(-e[i].b, i));
}
cur = w;
long long res = inf;
for (int i = 0; i < m; i++)
if (e[i].y == n - 1 && dist[i] != -1) res = min(res, getval(i));
return res < inf ? res : -1;
}
