#include<bits/stdc++.h>
using namespace std;
const int maxn=1010,maxm=10010,maxk=100010;
int n,m,k,d[maxn],nm[maxn],f[maxk][maxn],pp[maxn];
struct aaa
{
	int t,a,b;
}a[maxm];
bool cmp(aaa x,aaa y)
{
	if(x.a!=y.a)return x.a<y.a;
	return x.t<y.t;
}

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",&a[i].t,&a[i].a,&a[i].b);
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++)
		nm[a[i].a]=max(a[i].t,nm[a[i].a]);
	for(int i=1;i<=m;i++)
		for(int j=a[i].a;j<a[i].b;j++)
			pp[j]++;
	for(int i=0;i<=k;i++)
		f[i][1]=nm[1];
	for(int i=1;i<=k;i++)
		for(int j=1;j<=n;j++)
		{
			f[i][j]=min(f[i-1][j-1]+(d[j-1]-1)*pp[i-1],f[i][j-1]+d[j-1]*pp[i-1]);
			if(i-d[j-1]>=0)f[i][j]=min(f[i][j],f[i-d[j-1]][j-1]+d[j-1]*pp[i-1]);
		}
	printf("%d",f[k][n]);
	return 0;
}