#include <bits/stdc++.h>
#define ll long long
#define re register
#define MAXN 10005
#define mod 10007
#define inf 0x3f3f3f3f
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
#define inl inline
//#pragma GCC optimize (2)
//#pragma G++ optimize (2)
//#pragma comment(linker, "/STACK:1024000000,1024000000")
//不要在意那么多头文件
using namespace
std;
inline ll read()
{
re ll x =
0; re int f = 1
;
char ch = getchar
();
while(ch<'0'||ch>'9') { if(ch=='-') f = -1; ch = getchar
(); }
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=getchar
();}
return
x * f;
}
inline void write(ll x)
{
if(x>=10)write(x/10
);
putchar(x%10+'0'
);
}
inline void writeln(ll x)
{
write(x); puts(""
);
}
//读优+输出优化
ll last[MAXN],In[MAXN],Out[MAXN];
struct Node
{
ll t,b,e;
}e[MAXN];
ll ssw[MAXN],d[MAXN],sum[MAXN];
ll tim[MAXN],rang[MAXN],n,m,k;
int main()
{
n=
read(),m=read(),k=read
();
re ll ans=
0
;
for(re ll i=1
;i<n;i++) {
d[i]=
read
();
}
for(re ll i=1
;i<=m;i++) {
e[i].t=
read(),e[i].b=read(),e[i].e=read
();
last[e[i].b]=
max
(e[i].t,last[e[i].b]);
In[e[i].b]+=
1;//可以忽略
Out[e[i].e]+=
1;//划重点，下车的人数
}
last[n]=inf;
for(re ll i=1
;i<n;i++){
tim[i+
1]=max
(tim[i],last[i])+d[i];
ssw[i]=ssw[i
-1]+In[i]-Out[i];//完全没用，打着玩的，，
}
for(re ll i=1;i<=n;i++) sum[i]=sum[i-1]+Out[i];//划重点，前缀和
for(re ll i=1
;i<=m;i++){ans+=tim[e[i].e]-e[i].t;}
while(k--){//每次用一个，美滋滋
ll maxn=
0,flag;rang[n-1
]=n;
for(re ll i=n-2
;i;i--){
if(tim[i+1]>last[i+1]) rang[i]=rang[i+1
];
else rang[i]=i+1
;
}
//求rang[i](如果在i站等人，那么只影响下一站下的，反之会影响到rangi+1
for (re ll i=1
;i<n;i++){
if
(sum[rang[i]]-sum[i]>maxn&&d[i]){
maxn=sum[rang[i]]-sum[i],flag=i;
}
//找最优的一段
}
if(!maxn) break
;
ans-=maxn;
d[flag]-=
1;//更新d
tim[
1]=0
;
for(re ll i=1;i<n;i++){tim[i+1]=max(tim[i],last[i])+d[i];}//更新tim[i]
}
writeln(ans);//输出
return 0
;
}
