#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 long long INF = 1e18;
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) {
vector<int> ordA(M);
iota(ordA.begin(), ordA.end(), 0);
sort(ordA.begin(), ordA.end(), [&](int u, int v) {
return A[u] < A[v];
});
auto qry = [&](int i, int j) {
int res = 0;
for (int it = 0; it < W; ++it) {
res += i < L[it] && R[it] < j;
}
return res;
};
vector<long long> f(M, INF);
for (int i = 0; i < M; ++i) {
int id = ordA[i];
if (X[id] == 0) {
f[id] = 1LL * T[0] * qry(0, A[id]);
}
for (int j = i - 1; j >= 0; --j) {
int ind = ordA[j];
if (B[ind] <= A[id] && Y[ind] == X[id]) {
minimize(f[id], f[ind] + 1LL * T[X[id]] * qry(B[ind], A[id]));
}
}
f[id] = min(INF, f[id] + C[id]);
}
const int MAX = 1e9 + 7;
long long res = INF;
for (int i = 0; i < M; ++i) {
if (Y[i] == N - 1) {
res = min(res, f[i] + 1LL * T[N - 1] * qry(B[i], MAX));
}
}
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));
// }
