C++ :

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1010,M=10010;
int n,m,k,ans,d[N],last[N],arrive[N],indeg[N],effect[N];
int main() {
	scanf("%d%d%d",&n,&m,&k);
	for(int i=2;i<=n;i++)scanf("%d",&d[i]);
	for(int i=0;i<m;i++) {
		int t,a,b;
		scanf("%d%d%d",&t,&a,&b);
		indeg[b]++;
		last[a]=max(last[a],t);
		ans-=t;
	}
	for(int i=2;i<=n;i++)arrive[i]=max(arrive[i-1],last[i-1])+d[i];
	while(k--) {
		for(int i=n;i>=2;i--)
			if(!d[i])effect[i]=0;
			else {
				effect[i]=indeg[i];
				if(arrive[i]>last[i])effect[i]+=effect[i+1];
			}
		int Max=0,tt;
		for(int i=2;i<=n;i++)if(Max<effect[i]) {
			Max=effect[i]; tt=i;
		}
		if(!Max)break;
		d[tt]--;
		for(int i=tt;i<=n;i++)arrive[i]=max(arrive[i-1],last[i-1])+d[i];
	}
	for(int i=2;i<=n;i++)ans+=indeg[i]*arrive[i];
	printf("%d\n",ans);
	return 0;
}