1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 const int M=100005,N=1005;
 5 int n,m,k,i,j,mx,ans,t[M],off[M],last[M],come[M],down[M],dist[N];
 6 
 7 int read()
 8 {
 9     int x=0;
10     char ch=getchar();
11     while (ch<‘0‘ || ch>‘9‘) ch=getchar();
12     while (ch>=‘0‘ && ch<=‘9‘) x=(x<<1)+(x<<3)+ch-48,ch=getchar();
13     return x;
14 }
15 
16 int main()
17 {
18     n=read(),m=read(),k=read();
19     for (i=1;i<n;i++) dist[i]=read();
20     for (i=1;i<=m;i++) t[i]=read(),last[j=read()]=max(last[j],t[i]),off[down[i]=read()]++;
21     for (i=1;i<n;i++) come[i+1]=max(come[i],last[i])+dist[i];
22     for (i=1;i<=m;i++) ans+=come[down[i]]-t[i];
23     while (k--)
24     {
25         for (i=1;i<=n;i++) t[i]=0;
26         for (i=1;i<n;i++)
27             if (dist[i])
28                 for (j=i+1;j<=n;j++)
29                 {
30                     t[i]+=off[j];
31                     if (come[j]<=last[j]) break;
32                 }
33         mx=0;
34         for (i=1;i<n;i++)
35             if (t[i]>mx) mx=t[i],j=i;
36         dist[j]--,ans-=t[j],come[++j]--;
37         for (;j<n;j++) come[j+1]=max(come[j],last[j])+dist[j];
38     }
39     printf("%d\n",ans);
40     return 0;
41 }