#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
struct SEGMENT {
int l, r, v, maxv, p;
};
int N, M, K, Ans;
// Arr是到达时间， Sat是出发时间
int Arr[1005], Sat[1005], Out[1005], Man[1005], D[1005];
int main () {

ios::sync_with_stdio(false);
cin >> N >> M >> K;
for(int i=1; i<N; i++) cin >> D[i];
for(int i=1, t, a, b; i<=M; i++) {
cin >> t >> a >> b;
// 先减去每个人 "上车前的时间" ，后面直接用 "到达时间*到达人数" 整体计算消耗时间，从而优化程序
Ans-=t;
Out[b]++;
Sat[a]=max(Sat[a], t);
}
while(K--) {

memset(Man, 0, sizeof(Man));

for(int i=1; i<=N; i++) Arr[i]=max(Arr[i-1], Sat[i-1])+D[i-1];
// 从 "后缀" 开始寻找当前路径上正在运输的人数
for(int i=N; i>1; i--) {
if (D[i-1]) {
Man[i-1]=Out[i];
if (Arr[i]>Sat[i]) Man[i-1]+=Man[i];

}
else Man[i-1]=0;
}
int maxm=0, p=0;
for(int i=1; i<=N; i++)
if (Man[i]>maxm) {
maxm=Man[i];
p=i;

}
if (!p) break;
D[p]--;

}
for(int i=1; i<=N; i++) Arr[i]=max(Arr[i-1], Sat[i-1])+D[i-1];
for(int i=1; i<=N; i++) Ans+=Arr[i]*Out[i];
cout << Ans;
return 0;

}