type person=record
     t,x,y:longint;
	 end;
var num,sum,arrive,maxt,mint,d:array[0..10100]of longint;
    pp,i,j,n,m,k,ans:longint;
	p:array[1..10100]of person;
function max(x,y:longint):longint;
begin
if x>y then exit(x) else exit(y);
end;
begin
assign(input,'bus.in');reset(input);
assign(output,'bus.out');rewrite(output);
read(n,m,k);
ans:=0;
fillchar(num,sizeof(num),0);
fillchar(arrive,sizeof(arrive),0);
fillchar(mint,sizeof(mint),0);
fillchar(d,sizeof(d),0);
for i:=1 to n-1 do read(d[i]);
for i:=1 to m do
begin
read(p[i].t,p[i].x,p[i].y);
mint[p[i].x]:=max(mint[p[i].x],p[i].t);
inc(num[p[i].y-1]);
end;
for i:=1 to n-1 do mint[i+1]:=max(mint[i+1],mint[i]);
for i:=1 to n-1 do arrive[i+1]:=max(arrive[i],mint[i])+d[i];
for i:=1 to m do ans:=ans+arrive[p[i].y]-p[i].t;
for i:=1 to k do
begin
for j:=n-1 downto 1 do sum[j]:=num[j];
for j:=n-1 downto 1 do if arrive[j+1]>mint[j+1] then inc(sum[j],sum[j+1]);
pp:=0;
for j:=1 to n-1 do
if (d[j]>0)and(sum[j]>sum[pp]) then pp:=j;
if pp=0 then break;
ans:=ans-sum[pp];dec(d[pp]);
for j:=pp to n-1 do arrive[j+1]:=max(arrive[j],mint[j])+d[j];
end;
write(ans);
close(input);close(output);
end.