#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10,maxm=1e4+10;
int n,m,k,cnt,tot;
int p[maxn],tr[maxn],s[maxn],Sp[maxn],Se[maxn],S[maxn],r[maxm][3];
struct lo{
	int sum,num;
}l[maxn];
struct edge{
	int from,to,v;
}e[maxn];
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=((x<<1)+(x<<3))+c-'0';
		c=getchar();
	}
	return x*f;
}
inline int lowbit(int x){
	return x&-x;
}
inline void add(int x,int k){
	for(;x<=n;x+=lowbit(x))tr[x]+=k;
}
inline int ask(int x){
	int sum=0;
	for(;x;x-=lowbit(x))sum+=tr[x];
	return sum;
}
inline void build(int a,int b,int c){
	e[++cnt].from=a;
	e[cnt].to=b;
	e[cnt].v=c;
}
bool cmp(lo a,lo b){
	return a.sum<b.sum;	
}
inline void Init(){
	int a,b,c;
	n=read(),m=read(),k=read();
	for(int i=1;i<n;i++){
		c=read();
		build(i,i+1,c);
	}
	for(int i=1;i<=m;i++){
		c=read(),a=read(),b=read();
		r[i][2]=c;
		p[a]=max(p[a],c);
		s[a]++,s[b]--;
		r[i][0]=a;r[i][1]=b;
	}
	for(int i=1;i<=n;i++){
		add(i,s[i]);
		Sp[i]=p[i];
		if(i<n) Se[i]=Se[i-1]+e[i].v;
		if(S[i-1]<p[i])
		S[i]=p[i]+e[i].v;
		else 
		S[i]=S[i-1]+e[i].v;
	}
	for(int i=1;i<=m;i++){
		for(int j=r[i][0];j<=r[i][1];j++){
			tot+=e[i].v;
			if(tot<=p[j])
			tot+=p[j]-tot;
		}
		cout<<tot<<endl;
	}
	for(int i=1;i<n;i++){
		l[i].sum=ask(i);
		l[i].num=i;
	}
	cout<<tot<<endl;
}
inline void Work(){
	sort(l+1,l+n,cmp);
	for(int i=1;k>0&&i<n;k-=e[l[i].num].v,i++){
		if(k<e[l[i].num].v)tot-=l[i].sum*k;
		else tot-=l[i].sum*e[l[i].num].v;
	}
	printf("%d\n",tot);
}
int main(){
	Init();
	Work();
	return 0;
}