#include<cstdio>

#include<cstdlib>

#include<cstring>

#define max(a,b) (a > b ? a : b)

#define maxn 1000

#define maxm 10000

int n,m,k,ans=;

int d[maxn+],g[maxn+],sum[maxn+],las[maxn+],get[maxn+];

int t[maxm+],a[maxm+],b[maxm+];

inline void read()

{

     scanf("%d%d%d",&n,&m,&k);//分别表示景点数、乘客数和氮气加速器个数。

     int i;

     for (i=; i<n; i++)

         scanf("%d",&d[i]);//表示从第i 个景点开往第i+1 个景点所需要的时间，即Di。

     for (i=; i<=m; i++)

     {

         scanf("%d%d%d",&t[i],&a[i],&b[i]);//第i 位乘客来到出发景点的时刻，出发的景点编号和到达的景点编号。

         sum[b[i]]++;  //每个景点的人数

         las[a[i]]=max(las[a[i]],t[i]);  //Hash  储存出发的时间  max（ 到达景点最晚的时间，第i位乘客到达的时间 ）

     }

 }

inline void work()

{

     int i,maxs=,l,r;

     for (i=; i<=n; i++)

         if (sum[g[i]]-sum[i]>maxs&&d[i]>)//sum[第i站使用氮气影响到第几站]-sum[第i站]  即第i站使用氮气影响到最后一站的人数减去第i站使用氮气的人数

         {

             maxs=sum[g[i]]-sum[i];  //maxs= 第i站使用氮气影响到最后一站的人数减去第i站使用氮气的人数

             l=i;     //起点

             r=g[i];  //终点

         }

     if (r>n-)

        r=n-;

     d[l]--;

     ans-=maxs;

     for (i=l; i<=r; i++)

         get[i]=max(get[i-],las[i-])+d[i-];

     for (i=r; i>=l; i--)

         if (get[i+]<=las[i+]) g[i]=i+;

         else  g[i]=g[i+];

 }

inline void print()

{

     int i;

     for(i=;i<=n;i++)

         get[i]=max(get[i-],las[i-]) +d[i-];//  max(到达第i站的时间，最后一位乘客到达的时间)+路程所需的时间

     g[n-]=g[n]=n;//  g数组储存在第i战使用氮气    将影响到第几站

     for (i=n-; i>; i--) //

         if (get[i+]<=las[i+])//到达的时间小于最后一位乘客到达的时间，则不影响下一站以后的时间

             g[i]=i+;     //只影响到下一站

         else

             g[i]=g[i+]; // 从后向前循环  g[i]=下一站所影响到第几站

     for (i=; i<=n; i++)

         sum[i]+=sum[i-];//处理前缀和   sum表示每个景点的人数

     for (i=; i<=m; i++)//第i个人

         ans+=get[b[i]]-t[i];//（公交到达第b[i]站时间--第i个人到站的时间） 1

     for (i=; i<k; i++)

         work();

     printf("%d\n",ans);

 }

int main()

{

    read();

    print();

    return ;

}