代码如下：

#include<bits/stdc++.h>
#define N 1005
#define M 10005
using namespace std;
int n,m,k,d[N],t[M],a[M],b[M],last[N],sum[N],f[N],g[N],ans;
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++) scanf("%d%d%d",&t[i],&a[i],&b[i]),last[a[i]]=max(last[a[i]],t[i]),sum[b[i]]++;
	for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
	f[1]=last[1];
	for(int i=2;i<=n;i++) f[i]=max(f[i-1],last[i-1])+d[i-1];
	for(int i=1;i<=n;i++) ans+=f[b[i]]-t[i];
	while(k--){
		g[n-1]=n;
		for(int i=n-2;i>=1;i--){
			if(last[i+1]>=f[i+1]) g[i]=i+1;
			else g[i]=g[i+1];
		}
		int maxs=0,k=0;
		for(int i=1;i<n;i++){
			int t=sum[g[i]]-sum[i];
			if(t>maxs&&d[i]){
				maxs=t;
				k=i;
			}
		}
		ans-=maxs;
		d[k]--;
		for(int i=2;i<=n;i++) f[i]=max(f[i-1],last[i-1])+d[i-1];
	}
	printf("%d",ans);
	return 0;
}