#include <bits/stdc++.h>
#include "train.h"
using namespace std;
#define fi first
#define se second
#define left ___left___
#define right ___right___
#define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u)
#define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
namespace std {
template <class U, class V> scan_op(pair <U, V>) { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream &print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class...U> print_op(tuple <U...>) { return print_tuple_utils<0, tuple <U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))>typename enable_if <!is_same<Con, string>::value, ostream &>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class T> print_op(stack <T>) { vector <T> v; stack <T> st = u; while (!st.empty()) v.push_back(st.top()), st.pop(); reverse(v.begin(), v.end()); return out << v; }
template <class T> print_op(queue <T>) { queue <T> q = u; out << '{'; while (!q.empty()) { out << q.front(); q.pop(); if (!q.empty()) out << ", "; } out << '}'; return out; }
template <class T, class X, class Y> print_op(priority_queue <T, X, Y>) { priority_queue <T, X, Y> pq = u; out << '{'; while (!pq.empty()) { out << pq.top(); pq.pop(); if (!pq.empty()) out << ", "; } out << '}'; return out; }
}
template <class A, class B> bool minimize(A &a, B b) { return a > b ? a = b, true : false; }
template <class A, class B> bool maximize(A &a, B b) { return a < b ? a = b, true : false; }
const int MAX = 1e5 + 5, BL = 320, SZ = MAX / BL + 3;
const long long INF = 1e18;
int bk[MAX], lt[SZ], rt[SZ], cnt[MAX], lz[SZ], col[MAX];
long long Min[SZ][MAX], cost[MAX], val[MAX], dp[MAX];
void upd(int id) {
for (int i = lt[id]; i <= rt[id]; ++i) {
Min[id][col[i]] = INF;
cnt[i] += lz[id];
}
for (int i = lt[id]; i <= rt[id]; ++i) {
Min[id][col[i]] = min(Min[id][col[i]], cnt[i] * val[i] + cost[i]);
}
lz[id] = 0;
}
void add(int i) {
if (i < 0) {
return;
}
int id = bk[i];
for (int j = i; j >= lt[id]; --j) {
++cnt[j];
}
upd(id);
for (int j = id - 1; ~j; --j) {
++lz[j];
}
}
long long qry(int i, int ind, int T) {
if (i < 0) {
return INF;
}
int id = bk[i];
long long res = INF;
for (int j = i; j >= lt[id]; --j) {
if (col[j] == ind) {
res = min(res, 1LL * (cnt[j] + lz[id]) * T + cost[j]);
}
}
for (int j = id - 1; j >= 0; --j) {
res = min(res, Min[j][ind] + 1LL * lz[j] * T);
}
return res;
}
template<class T>
int lwb(const vector<T> &v, const T &x) {
return lower_bound(v.begin(), v.end(), x) - v.begin();
}
template<class T>
int upb(const vector<T> &v, const T &x) {
return upper_bound(v.begin(), v.end(), x) - v.begin();
}
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) {
for (int i = 0; i < M; ++i) {
bk[i] = i / BL;
rt[bk[i]] = i;
}
for (int i = M - 1; ~i; --i) {
lt[bk[i]] = i;
}
for (int i = 0; i <= bk[M - 1]; ++i) {
for (int j = 0; j < N; ++j) {
Min[i][j] = INF;
}
}
vector<int> ordB(M);
iota(ordB.begin(), ordB.end(), 0);
sort(ordB.begin(), ordB.end(), [&](int u, int v) {
return B[u] < B[v];
});
for (int i = 0; i < M; ++i) {
col[i] = Y[ordB[i]];
val[i] = T[col[i]];
cost[i] = INF;
}
auto BB = B;
sort(BB.begin(), BB.end());
vector<int> ordA(M);
iota(ordA.begin(), ordA.end(), 0);
sort(ordA.begin(), ordA.end(), [&](int u, int v) {
return A[u] < A[v];
});
vector<int> posB(M);
for (int i = 0; i < M; ++i) {
posB[ordB[i]] = i;
}
vector<int> ordW(W);
iota(ordW.begin(), ordW.end(), 0);
sort(ordW.begin(), ordW.end(), [&](int u, int v) {
return R[u] < R[v];
});
int j = 0;
for (int id : ordA) {
dp[id] = INF;
while (j < W && R[ordW[j]] < A[id]) {
int id = ordW[j++];
add(lwb(BB, L[id]) - 1);
}
if (X[id] == 0) {
minimize(dp[id], 1LL * j * T[0]);
}
minimize(dp[id], qry(upb(BB, A[id]) - 1, X[id], T[X[id]]));
dp[id] = min(INF, dp[id] + C[id]);
cost[posB[id]] = dp[id];
upd(bk[posB[id]]);
}
while (j < W) {
int id = ordW[j++];
add(lwb(BB, L[id]) - 1);
}
long long res = qry(M - 1, N - 1, T[N - 1]);
return res == INF ? -1 : res;
}
// signed main() {
// file("TRAIN");
// int N, M, W;
// assert(3 == scanf("%d %d %d", &N, &M, &W));
// std::vector<int> t(N);
// std::vector<int> x(M);
// std::vector<int> y(M);
// std::vector<int> a(M);
// std::vector<int> b(M);
// std::vector<int> c(M);
// std::vector<int> l(W);
// std::vector<int> r(W);
// for (int i = 0; i < N; i++)
// assert(1 == scanf("%d", &t[i]));
// for (int i = 0; i < M; i++)
// assert(5 == scanf("%d %d %d %d %d", &x[i], &y[i], &a[i], &b[i], &c[i]));
// for (int i = 0; i < W; i++)
// assert(2 == scanf("%d %d", &l[i], &r[i]));
// printf("%lld", solve(N, M, W, t, x, y, a, b, c, l, r));
// }
