#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5, N2 = 1e4 + 5;
int n, m, k, d[N], maxn[N], e[N], ar[N], sum[N], t[N2], a[N2], b[N2], ans = 0;
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i < n; ++i) cin >> d[i];
	for (int i = 1; i <= m; ++i) {
		cin >> t[i] >> a[i] >> b[i];
		maxn[a[i]] = max(maxn[a[i]], t[i]);
		++e[b[i]];
	}
	for (int i = 2; i <= n; ++i) ar[i] = max(ar[i - 1], maxn[i - 1]) + d[i - 1];
	for (int i = 1; i <= m; ++i) ans += ar[b[i]] - t[i];
	cout << ans << endl;
	while (k--) {
		for (int i = 1; i <= n; ++i) sum[i] = 0;
		int w = 0;
		for (int i = n - 1; i >= 1; --i) {
			if (d[i] <= 0) continue;
			sum[i] = e[i + 1];
			if (ar[i + 1] > maxn[i + 1]) sum[i] += sum[i + 1];
			if (sum[i] > sum[w]) w = i;
		}
		ans -= sum[w];
		--d[w];
		for (int i = w + 1; i <= n; ++i) {
			--ar[i];
			if (ar[i] < maxn[i]) break;
		}
	}
	cout << ans << endl;
	return 0;
}