如题。

#include <bits/stdc++.h>
#define fs first
#define sc second
#define ls tr[u].ch[0] 
#define rs tr[u].ch[1]
#define mid ((l + r) >> 1)
#define lc ls, l, mid
#define rc rs, mid + 1, r
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)
#define gc getchar
#define pc putchar

using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using ll = long long;

const int maxn = 1e6 + 10;
const ll inf = 4e18;
const bool multidata = 0;

int read() {
	int x = 0, f = 1; char c = gc();
	while (c < '0' || c > '9') { if (c == '-') f = -f; c = gc(); }
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc();
	return x * f;
}

void write(ll x) {
	if (x < 0) pc('-'), x = -x;
	if (x < 10) return void (pc(x + '0'));
	write(x / 10), pc(x % 10 + '0');
}

struct edge {
	int u, v, p, q, w, id;
};

struct op {
	int j, l, r;
};

struct QwQ {
	vector<op> q;
	int hd = 0, tl = -1;
	void push_back(op x) { q.push_back(x), ++tl; }
	void pop_back() { q.pop_back(), --tl; }
};

struct node {
	int ch[2] = {};
	int sum = 0;
};

node tr[maxn * 22];
int rt[maxn], tot;

void modify(int &u, int pre, int l, int r, int p, int k) {
	tr[u = ++tot] = tr[pre];
	if (l == r) {
		tr[u].sum += k;
		return;
	}
	if (p <= mid) modify(ls, tr[pre].ch[0], l, mid, p, k);
	else modify(rs, tr[pre].ch[1], mid + 1, r, p, k);
	tr[u].sum = tr[ls].sum + tr[rs].sum;
}

int query(int u, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr) return tr[u].sum;
	int ans = 0;
	if (ql <= mid) ans += query(lc, ql, qr);
	if (qr > mid) ans += query(rc, ql, qr);
	tr[u].sum = tr[ls].sum + tr[rs].sum;
	return ans;
}

ll solve(int n, int m, int w, vi t, vi x, vi y, vi a, vi b, vi c, vi l, vi r) {
	vector<edge> e (m + 2), ej (m + 2); vector<ll> f (m + 2);
	vector<QwQ> que(n); vector<int> buc;
	vector<pii> rg;
	e[0] = {0, 0, 0, 0, 0, 0};
	f[0] = 0;
	rep(i, 0, m - 1) e[i + 1] = {x[i], y[i], a[i], b[i], c[i], i + 1};
	e[m + 1] = {n - 1, n - 1, (int) 1e9 + 1, (int) 1e9 + 1, 0, m + 1};
	rep(i, 0, m + 1) b.push_back(e[i].p), b.push_back(e[i].q);
	rep(i, 0, w - 1) b.push_back(l[i]), b.push_back(r[i]);
	sort(b.begin(), b.end());
	b.resize(unique(b.begin(), b.end()) - b.begin());
	rep(i, 0, m + 1) {
		e[i].p = lower_bound(b.begin(), b.end(), e[i].p) - b.begin() + 1;
		e[i].q = lower_bound(b.begin(), b.end(), e[i].q) - b.begin() + 1;
	}
	rep(i, 0, w - 1) {
		l[i] = lower_bound(b.begin(), b.end(), l[i]) - b.begin() + 1;
		r[i] = lower_bound(b.begin(), b.end(), r[i]) - b.begin() + 1;
		rg.push_back({r[i], l[i]});
	}
	sort(rg.begin(), rg.end());
	rep(i, 0, w - 1) modify(rt[i + 1], rt[i], 0, b.size() + 5, rg[i].sc, 1);
	rep(i, 1, m + 1) f[i] = inf;
	ej = e;
	sort(e.begin(), e.end(), [] (edge x, edge y) {
		return x.p < y.p;
	});
	sort(ej.begin(), ej.end(), [] (edge x, edge y) {
		return x.q < y.q;
	});
	auto val = [&] (int i, int j) -> ll {
		ll ans = f[ej[j].id] + e[i].w;
		int l = ej[j].q + 1, r = e[i].p - 1;
		ll cnt = 0; pii tmp = {r, 1e9};
		auto id = upper_bound(rg.begin(), rg.end(), tmp) - rg.begin();
		cnt = query(rt[id], 0, b.size() + 5, l, b.size() + 5);
		return ans + cnt * t[e[i].u];
	};
	int mxj = 0;
	rep(i, 1, m + 1) {
//		cout << i << endl;
		while (mxj <= (int) ej.size() - 1 && ej[mxj].q <= e[i].p) {
			int x = ej[mxj].v;
			while (que[x].hd <= que[x].tl && val(que[x].q[que[x].tl].l, mxj) <= val(que[x].q[que[x].tl].l, que[x].q[que[x].tl].j)) que[x].pop_back();
			if (que[x].hd > que[x].tl) {
				que[x].push_back({mxj, i, m + 1});
				++mxj;
				continue;
			}
			int l = que[x].q[que[x].tl].l, r = que[x].q[que[x].tl].r + 1;
			while (l < r) {
				if (val(mid, mxj) <= val(mid, que[x].q[que[x].tl].j)) r = mid;
				else l = mid + 1;
			}
			que[x].q[que[x].tl].r = l - 1;
			if (l <= m + 1) que[x].push_back({mxj, l, m + 1});
			++mxj;
		}
		int x = e[i].u;
		while (que[x].hd <= que[x].tl && que[x].q[que[x].hd].r < i) que[x].hd++;
		if (que[x].hd > que[x].tl) continue;
		int j = que[x].q[que[x].hd].j;
		f[e[i].id] = val(i, j);
//		cout << "! " << e[i].id << " " << ej[j].id << " " << f[e[i].id] << endl;
		que[x].q[que[x].hd].l = i;
	}
	return f[m + 1] == inf ? -1 : f[m + 1];
}

void fake_main() {
	int N = read(), M = read(), W = read();
	vi T (N), X (M), Y (M), A (M), B (M), C (M), L (W), R (W);
	rep(i, 0, N - 1) T[i] = read();
	rep(i, 0, M - 1) X[i] = read(), Y[i] = read(), A[i] = read(), B[i] = read(), C[i] = read();
	rep(i, 0, W - 1) L[i] = read(), R[i] = read();
	write(solve(N, M, W, T, X, Y, A, B, C, L, R));
}

signed main() {
	int T = multidata ? read() : 1;
	while (T--) fake_main();
	return 0;
}
/*
3 3 1 
20 30 40
0 1 1 15 10
1 2 20 30 5
0 2 18 40 40
16 19
*/