C++ :

#include<cstdio>
#include<algorithm>

#define MAXM 10010
#define MAXN 1010 
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))

using namespace std;

int n,m,tt,sum[MAXN],d[MAXN],dise[MAXN],disb[MAXN],com[MAXN],st[MAXN],lat[MAXN];
int g[MAXN],r[MAXN];

struct at{
	int cm,l,r;
}peo[MAXM];

struct AT{
	int w,o;
}cit[MAXN];

int main()
{
	scanf("%d%d%d",&n,&m,&tt);
	for(int i=1;i<n;i++){
		scanf("%d",&d[i]);
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&peo[i].cm,&peo[i].l,&peo[i].r);
		if(peo[i].cm>lat[peo[i].l]){
			lat[peo[i].l]=peo[i].cm;
		}
		sum[peo[i].r]++;
		st[peo[i].r]+=peo[i].cm;
	}
	int Ans=0;
	for(int i=1;i<=n;i++){
		dise[i]=disb[i-1]+d[i-1];
		Ans+=(dise[i])*sum[i]-st[i];
		disb[i]=MAX(dise[i],lat[i]);
	}
	if(tt==0)
		printf("%d",Ans);
	else{
		for(int gs=1;gs<=tt;gs++){
			Ans=0;
			r[n]=0;
			int t=0;
			for(int i=n-1;i>0;i--){
				if(dise[i+1]>lat[i+1]){
					r[i]=r[i+1]+sum[i+1];
				}else{
					r[i]=sum[i+1];
				}
				if(r[i]>r[t]&&d[i]>0)	t=i;
			}
			d[t]--;
			//printf("%d %d %d \n",t,r[t],dise[t+1]);
			for(int i=t+1;i<=n;i++){
				dise[i]=disb[i-1]+d[i-1];
				disb[i]=MAX(dise[i],lat[i]);
			}
			for(int i=1;i<=n;i++){
				Ans+=dise[i]*sum[i]-st[i];
			}
			//printf("%d \n",Ans);
		}
		Ans=0;
		for(int i=1;i<=n;i++){
			Ans+=dise[i]*sum[i]-st[i];
		}
		printf("%d",Ans);
	}
	getchar();getchar();
	return 0;
}