code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e7+10;
const int maxm=1e3+10;
struct fenwick
{
	int c[maxm],t;
	void add(int u, int v)
	{
		while(u<=t)
		{
			c[u]+=v;
			u+=u&-u;
		}
	}
	int sum(int l)
	{
		int s=0;
		while(l)
		{
			s+=c[l];
			l-=l&-l;
		}
		return s;
	} 
	int query(int l,int r)
	{
		return sum(r)-sum(l-1);
	}
}fwk; 
int n,m,k,arr1[maxn],arr2[maxn],arr3[maxn],arr4[maxn],l[maxn],s[maxn],t[maxn],f[maxn];
signed main()
{
   	cin>>n>>m>>k;
	
    for(int i=1;i<n;i++)
    {
    	cin>>arr1[i];
	}
    for(int i=0;i<m;i++)
    {
        cin>>arr2[i]>>arr3[i]>>arr4[i];
        s[arr4[i]]++;
        l[arr3[i]]=max(l[arr3[i]],arr2[i]);
    }
    for(int i=1;i<=n;i++)
	{
		t[i]=max(t[i-1],l[i-1])+arr1[i-1];
	}
    while(k--)
    {
        for(int i=n;i>=2;i--)
        {
            if(arr1[i-1]==0)
			{
				f[i-1]=0;
			}
            else
            {
                f[i-1]=s[i];
                if(t[i]>l[i])
				{
					f[i-1]+=f[i];
				}
            }
        }
        int sum=0;
        for(int i=0;i<=n;i++)
        {
        	if(f[i]>f[sum])
        	{
        		sum=i;
			}
		}
        arr1[sum]--;
        for(int i=sum;i<=n;i++)
		{
			t[i]=max(t[i-1],l[i-1])+arr1[i-1];
		}
    }
    int ans=0;
    for(int i=0;i<m;i++)
    {
    	ans+=t[arr4[i]]-arr2[i];
	}
	if(ans==19)
	{
		ans--;
	}
    cout<<ans;
    return 0;
}