$30分 除hack和前七个点外WA.$ $本蒟蒻认为自己想到了正解欣喜若狂，但是调了两个小时代码始终无法完善自己的细节。悲痛欲绝。$

//noip 2011 d2t3

// 首先, 答案是∑(T达 - T到) = ∑T达 - ΣT到，后者已知，故需要令前者最小

//不同人可能需要到达相同的某个站, 则到达该站的人数我们称作该站的权值

//对于某人, 当他在Ti时刻来到Ai站, 车不能已经开走, 则有Ai站的离站时间T离(ai)需要 <= Ti
//			于是Ai 和 max_Ti构成限制条件 : 车离开Ai的时间T离(ai) = max(T限(ai)[即max_Ti], T达(ai))

//I. 我们考虑不使用加速器的情况, 对于站i, 其到达时间T达(i)等于T离(i - 1) + D(i - 1)
//									   其离站时间T离(i)等于max(T限(i), T达(i))
//II. 再考虑倘若使用加速器使得到达站i的时间提前 1 (D(i - 1) --)
//				此时(i T限 < T达 则T达减1的同时 T离的时间-1, 则这份加速能够向下传递, 即使T达(i + 1)减少1
//					(iiT限 >= T达 则T达减1的同时 T离的时间不变, 则这份加速不能向下传递

//此时, 以不能向下传递的站点作为分界线, 整条站线被分为t段连续区间；
//对每段区间内部, 选择在哪个站点加速
//		我们选择后面的站点带来的效益不如前面的站点, 所以我们选择最前面的站点, 对答案的贡献为区间权值和
//对于区间之间, 由于不可传递的站点的阻隔, 任意区间内部的时间变化不会影响前后的其他区间
//**基于以上两点, 我们总选择当下权值和最大的整段连续区间使用加速器, 使用次数为min{T达 - T限}
//													对答案的贡献为{该段权值和*使用次数}
//为了完成以上过程, 我们可以使用大根堆来维护一个个连续区间, 关键字为权值和
//则当对一个区间完成操作后, 该段区间会分裂, 分裂为数段小区间, 再加入堆中即可.

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1e3 + 10, M = 1e4 + 10, K = 1e5 + 10;
typedef long long LL;
typedef pair<int, int> PII;

struct Node{
	int l, r; //左右站点
	int rest; //还可总体操作几次
	LL val; //权和
	bool operator <(const Node &x)const{
		return val < x.val;
	}
};
priority_queue<Node> q;

int n, m, k;
int T[M], Td[N], Tl[N], Tx[N];
int cnt[N], s[N], d[N]; //权, 权的前缀和
LL sum, ans;

void init(){
	//求权的前缀和
	for(int i = 1; i <= n; i ++) s[i] = s[i - 1] + cnt[i];
	
	//进行递推
	for(int i = 1; i < n; i ++){
		Tl[i] = max(Td[i], Tx[i]);
		Td[i + 1] = Tl[i] + d[i];
		ans += Td[i + 1] * cnt[i + 1];
	}
	
	ans -= sum; //得到无加速器时的总时间
	
	//预处理出最初的连续区间	
	for(int i = 1, j; i <= n; i = j + 1){ //i是左端点 j是右端点
		j = i;
		int rest = Td[i]; //rest 是对所有达到的时间、所有还能传递次数、以及d[i - 1] 的min值, 即还能对这段区间加速几次
		while(j <= n && Td[j] > Tx[j]) rest = min(rest, Td[j] - Tx[j]), j ++;
		if(j <= n) rest = min(rest, Td[j]);
		int l = i, r = j > n ? j - 1 : j; //三目是考虑到j==n+1时右端点为n
		rest = min(rest, d[l - 1]);
		q.push({l, r, rest, s[r] - s[l - 1]}); //入堆
	}
}

void apart(Node x){ //对区间x实现分裂
	for(int i = x.l; i <= x.r; i ++) Td[i] -= x.rest, Tl[i] = max(Td[i], Tx[i]); //更新Td Tx
	for(int i = x.l, j; i <= x.r; i = j + 1){ //同预处理部分
		j = i;
		int rest = Td[i];
		while(j <= x.r && Td[j] > Tx[j]) rest = min(rest, Td[j] - Tx[j]), j ++;
		if(j <= x.r) rest = min(rest, Td[j]);
		int l = i, r = j > x.r ? j - 1 : j;
		rest = min(rest, d[l - 1]);		
		q.push({l, r, rest, s[r] - s[l - 1]});
	}
}

int main(){
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i < n; i ++) scanf("%d", &d[i]);
	for(int i = 1; i <= m; i ++){
		int t, a, b;
		scanf("%d%d%d", &t, &a, &b);
		Tx[a] = max(Tx[a], t), sum += t, cnt[b] ++;
	}
	
	init(); //跑一次无加速器情况
	
	while(q.size()){
		Node t = q.top();
		q.pop();
		
		if(k > t.rest){
			ans -= t.val * t.rest, k -= t.rest, d[t.l] -= t.rest;
			if(t.r > t.l) apart(t);
		}
		else{
			ans -= t.val * k;
			break;
		}
	}
	printf("%lld\n", ans);
	
	return 0;
}