#include<bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 2e6 + 5;
int n, m, k, d[MAXN], S[MAXN], down[MAXN], up[MAXN], Max[MAXN], pre[MAXN], L[MAXN], R[MAXN], tot, ans, seg[MAXN * 4], lazy[MAXN * 4];

void push_down(int x){
	seg[x << 1] += lazy[x];
	seg[x << 1 | 1] += lazy[x];
	lazy[x << 1] += lazy[x];
	lazy[x << 1 | 1] += lazy[x];
	lazy[x] = 0;
}

void change(int id, int l, int r, int fl, int fr, int val){
	if(fl <= l && r <= fr){
		seg[id] += val;
		lazy[id] += val;
		return ;
	}
	int mid = l + r >> 1;
	push_down(id);
	if(fl <= mid) change(id << 1, l, mid, fl, fr, val);
	if(fr > mid) change(id << 1 | 1, mid + 1, r, fl, fr, val);
	seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
}

int query(int id, int l, int r, int fl, int fr){
	if(fl > fr) return LONG_LONG_MAX;
	if(fl <= l && r <= fr) return seg[id];
	int res = LONG_LONG_MAX, mid = l + r >> 1;
	push_down(id);
	if(fl <= mid) res = query(id << 1, l, mid, fl, fr);
	if(fr > mid) res = min(query(id << 1 | 1, mid + 1, r, fl, fr), res);
	return res;
}

signed main(){
	cin >> n >> m >> k;
	for(int i = 1; i < n; i++) cin >> d[i];
	for(int i = 1; i <= m; i++){
		int t, a, b;
		cin >> t >> a >> b;
		up[a]++;
		down[b]++;
		if(t > Max[a]) ans += (t - Max[a]) * (up[a] - 1), Max[a] = t;
		else ans += Max[a] - t;
	}
	for(int i = 1; i <= n; i++) pre[i] = pre[i - 1] + down[i];
	bool fg = 1;
	for(int i = 1; i <= n; i++){
		S[i] = max(S[i - 1], Max[i - 1]) + d[i - 1];
		change(1, 1, n, i, i, S[i] - Max[i]);
		if(S[i - 1] - Max[i - 1] <= 0 && i != 1) R[tot] = i - 1, fg = 1;
		if(i != 1 && fg && d[i - 1] != 0) L[++tot] = i, fg = 0;
	}
	R[tot] = n;
	priority_queue<pair<int, pair<int, int> > > q;
	for(int i = 1; i <= tot; i++) q.push( {pre[R[i]] - pre[L[i] - 1], {L[i], R[i]}} );
	while(!q.empty() && k){
		k--;
		pair<int, pair<int, int> > pr = q.top(); q.pop();
		change(1, 1, n, pr.second.first, pr.second.second, -1);
		d[pr.second.first - 1]--;
		while(d[pr.second.first - 1] <= 0 && pr.second.first <= pr.second.second){
			pr.first -= down[pr.second.first];
			pr.second.first++;
		}
		if(pr.second.first > pr.second.second) continue;
		if(query(1, 1, n, pr.second.first, pr.second.second - 1) > 0) q.push(pr);
		else{
			int las = pr.second.first;
			for(int i = pr.second.first; i <= pr.second.second; i++)
				if(query(1, 1, n, i, i) <= 0) q.push( {pre[i] - pre[las - 1], {las, i}} ), las = i + 1;
		}
	}
	int num = 0;
	for(int i = 1; i < n; i++){
		num -= down[i];
		ans += max(-query(1, 1, n, i, i), 0ll) * num + max(query(1, 1, n, i, i), 0ll) * up[i];
		num += up[i];
		ans += num * d[i];
	}
	cout << ans;
	return 0;
}
/*
3 3 2
1 4 
0 1 3
1 1 2
5 2 3
*/