#include "train.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const long long INF = 1'000'000'000'000'000;
const ll INF32 = 1'000'000'001;
void upd(ll w, vector<long long>& all, ll c, ll nw, vector<pair<ll, ll>>& eat) {
for (ll i = 0; i < (1 << w); i++) {
bool b = false;
for (ll j = 0; j < w; j++) {
if (!((i >> j) & 1)) {
if (eat[j].first <= nw) {
all[i + (1 << j)] = min(all[i] + c, all[i + (1 << j)]);
}
if (eat[j].second < nw) {
b = true;
}
}
}
if (b) {
all[i] = INF;
}
}
}
struct BIT {
vector<ll> tree;
vector<ll> all;
BIT(vector<ll> a) {
all = a;
all.push_back(-1);
all.push_back(INF32);
sort(all.begin(), all.end());
tree.resize(all.size() + 1);
}
ll s(ll x) {
return lower_bound(all.begin(), all.end(), x) - all.begin();
}
void add(ll x) {
x = s(x);
x++;
for (; x < tree.size(); x += x & -x) {
tree[x]++;
}
}
ll get(ll l, ll r) {
return get(r) - get(l);
}
ll get(ll x) {
x = s(x);
ll ans = 0;
for (; x > 0; x -= x & -x) {
ans += tree[x];
}
return 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) {
if (W <= 10 && N <= 1000 && M <= 1000) {
vector<pair<ll, ll>> eat;
multiset<tuple<ll, ll, ll, long long, ll>> s;
for (ll i = 0; i < W; i++) {
eat.emplace_back(L[i], R[i]);
}
sort(eat.begin(), eat.end());
vector<vector<long long>> ans(N, vector<long long>(1 << W, INF));
ans[0][0] = 0;
for (ll i = 0; i < M; i++) {
s.emplace(A[i], 2, i, 0ll, 0);
}
while (!s.empty()) {
auto[nt, t, i, c, m] = *s.begin();
s.erase(s.begin());
if (t == 2) {
upd(W, ans[X[i]], T[X[i]], nt, eat);
ll nc = 0;
for (ll j = 0; j < W; j++) {
if (eat[j].first <= B[i] && eat[j].second >= nt) {
nc += 1 << j;
}
}
for (ll j = 0; j < (1 << W); j++) {
s.emplace(B[i], 1, i, C[i] + ans[X[i]][j], j | nc);
}
} else {
ans[Y[i]][m] = min(ans[Y[i]][m], c);
}
}
upd(W, ans.back(), T.back(), INF32, eat);
if (ans.back().back() >= INF) {
return -1;
}
return ans.back().back();
}
vector<pair<ll, ll>> eat;
multiset<tuple<ll, ll, ll, long long>> s;
vector<ll> all;
for (ll i = 0; i < W; i++) {
eat.emplace_back(R[i], L[i]);
s.emplace(R[i], 3, i, 0ll);
s.emplace(L[i], 0, 0, 0ll);
all.push_back(L[i]);
}
BIT bi(all);
sort(eat.begin(), eat.end());
vector<deque<pair<long long, pair<long long, long long>>>> nmaco(N);
nmaco[0].emplace_back(0, make_pair(0, 0));
for (ll i = 0; i < M; i++) {
s.emplace(A[i], 2, i, 0ll);
}
long long co = 0, maco = 0;
while (!s.empty()) {
auto[_, t, i, c] = *s.begin();
s.erase(s.begin());
if (t == 0) {
maco++;
continue;
}
if (t == 3) {
bi.add(L[i]);
co++;
continue;
}
if (t == 2) {
if (nmaco[X[i]].empty()) {
continue;
}
while (nmaco[X[i]].size() > 1 && nmaco[X[i]][0].first + (nmaco[X[i]][0].second.first + bi.get(nmaco[X[i]][0].second.second, INF32)) * T[X[i]] >= nmaco[X[i]][1].first + (nmaco[X[i]][1].second.first + bi.get(nmaco[X[i]][1].second.second, INF32)) * T[X[i]]) {
nmaco[X[i]].pop_front();
}
s.emplace(B[i], 1, i, C[i] + nmaco[X[i]].front().first + (nmaco[X[i]].front().second.first + bi.get(nmaco[X[i]].front().second.second, INF32)) * T[X[i]]);
} else {
c -= maco * T[Y[i]];
if (nmaco[Y[i]].empty() || nmaco[Y[i]].back().first > c) {
while (!nmaco[Y[i]].empty() && nmaco[Y[i]].back().second.first == maco) {
nmaco[Y[i]].pop_back();
}
nmaco[Y[i]].emplace_back(c, make_pair(maco, B[i] + 1));
}
}
}
if (nmaco.back().empty()) {
return -1;
}
while (nmaco.back().size() > 1 && nmaco.back()[0].first + (nmaco.back()[0].second.first + bi.get(nmaco.back()[0].second.second, INF32)) * T.back() >= nmaco.back()[1].first + (nmaco.back()[1].second.first + bi.get(nmaco.back()[1].second.second, INF32)) * T.back()) {
nmaco.back().pop_front();
}
if (nmaco.back().front().first + co * T.back() >= INF) {
return -1;
}
return nmaco.back().front().first + co * T.back();
}
#ifdef LOCAL
signed main() {
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));
}
#endif
