#include<bits/stdc++.h>
using namespace std;

const int N = 1010, M = 10010;

int n, m, k;
int d[N];
int t[M], a[M], b[M];
int last[N], sum[N];
int tm1[N], f[N];

int main()
{
    cin >> n >> m >> k;
    for(int i = 1; i < n; i++) cin >> d[i];
    for(int i = 0; i < m; i++)
    {
        cin >> t[i] >> a[i] >> b[i];
        last[a[i]] = max(last[a[i]], t[i]);
        sum[b[i]] ++;
    }

    for(int i = 1; i <= n; i++)
        tm1[i] = max(tm1[i - 1], last[i - 1]) + d[i - 1];

    while(k --)
    {
        for(int i = n; i >= 2; i--)
        {
            f[i - 1] = sum[i];
            if(tm1[i] > last[i])
                f[i - 1] += f[i];
        }

        int p = 0;
        for(int i = 1; i <= n; i++)
            if(d[i] && f[p] < f[i])
                p = i;
        
        d[p] --;
        for(int i = p; i <= n; i++)
            tm1[i] = max(tm1[i - 1], last[i - 1])  + d[i - 1];
    }

    int res = 0;
    for(int i = 0; i < m; i++)
        res += tm1[b[i]] - t[i];
    cout << res << endl;
    return 0;
}

/*
每个站台最早发车时间last[i] = 最后一个到达站台i的乘客的时间。
每个站台下车的人数 sum[i]
最早到达每个站台的时间tm[i]
tm[i] = max(tm[i - 1], last[i - 1]) + d[i - 1]
其中d[i - 1]是从第i-1个站台走到第i个站台的时间

乘客的旅行时间 tm[b[i]] - t[i].
b[i]是乘客的终点站，t[i]是乘客到达起点的时间

考虑每个加速器如何使用。
贪心策略：每次选择当前节约时间最多的一段即可。
*/