C++ :

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1010,M=10010;
int n,m,k,ans,d[N],last[N],arrive[N],indeg[N],effect[N];
int main() {
	scanf("%d%d%d",&n,&m,&k);
	for(int i=2;i<=n;i++)scanf("%d",&d[i]);
	for(int i=0;i<m;i++) {
		int t,a,b;
		scanf("%d%d%d",&t,&a,&b);
		indeg[b]++;
		last[a]=max(last[a],t);
		ans-=t;
	}
	for(int i=2;i<=n;i++)arrive[i]=max(arrive[i-1],last[i-1])+d[i];
	while(k--) {
		for(int i=n;i>=2;i--)
			if(!d[i])effect[i]=0;
			else {
				effect[i]=indeg[i];
				if(arrive[i]>last[i])effect[i]+=effect[i+1];
			}
		int Max=0,tt;
		for(int i=2;i<=n;i++)if(Max<effect[i]) {
			Max=effect[i]; tt=i;
		}
		if(!Max)break;
		d[tt]--;
		for(int i=tt;i<=n;i++)arrive[i]=max(arrive[i-1],last[i-1])+d[i];
	}
	for(int i=2;i<=n;i++)ans+=indeg[i]*arrive[i];
	printf("%d\n",ans);
	return 0;
}

Pascal :

program bus;
var
  n,m,k,i,j,sumt,tot,s:longint;
  d,ar,le,p,xc:array[0..1001]of longint;
  t,a,b:array[1..10001]of longint;
function max(a,b:longint):longint;
begin
  if a>b then exit(a);
  exit(b);
end;
procedure handle;
var
  i:longint;
begin
  fillchar(p,sizeof(p),0);
  for i:=1 to n-1 do
    ar[i+1]:=max(ar[i],le[i])+d[i];
  i:=1;
  s:=0;
  while i<=n-1 do
    begin
      if d[i]>0 then
        begin
          j:=i;
          p[j]:=xc[i+1];
          while ar[i+1]>le[i+1] do
            begin
              inc(i);
              p[j]:=p[j]+xc[i+1];
            end;
          if p[j]>p[s] then s:=j;
        end;
      inc(i);
    end;
  if p[s]=0 then
    begin
      k:=0;
      exit;
    end;
  {for i:=1 to n-1 do
    if (p[i]=p[s]) and (k>0) then
      begin
        dec(d[i]);
        dec(k);
      end;}  //!!slower
  dec(d[s]);dec(k);
end;
begin
  //assign(input,'bus.in');reset(input);
  //assign(output,'bus.out');rewrite(output);
  readln(n,m,k);
  for i:=1 to n-1 do
    read(d[i]);
  for i:=1 to m do
    begin
      read(t[i],a[i],b[i]);
      inc(xc[b[i]]);
      if t[i]>le[a[i]] then
        le[a[i]]:=t[i];
    end;
  while k>0 do
    handle;
  for i:=1 to n-1 do
    ar[i+1]:=max(ar[i],le[i])+d[i];
  sumt:=0;
  for i:=1 to m do
    sumt:=sumt+ar[b[i]]-t[i];
  writeln(sumt);
  //close(input);close(output);
end.