附代码：

program P658;

var n,m,k:longint;

d:array[0..1000] of integer;

time,f,sum,g:array[0..10000] of int64;

t:array[0..10000] of longint;

a,b:array[0..10000] of integer;

i,j,ll,maxs,maxj,l,r:longint;

ans:int64;

function max(a,b:longint):longint;

begin

if a>b then exit(a) else exit(b);

end;

begin

readln(n,m,k);

for i:=1 to n-1 do

read(d[i]);

readln;

fillchar(f,sizeof(f),0);

fillchar(sum,sizeof(sum),0);

for i:=1 to m do

begin

readln(t[i],a[i],b[i]);

inc(sum[b[i]]);

f[a[i]]:=max(f[a[i]],t[i]);

end;

for i:=2 to m do

sum[i]:=sum[i]+sum[i-1];

fillchar(time,sizeof(time),0);

time[1]:=0;

for i:=1 to n do

time[i]:=max(time[i-1],f[i-1])+d[i-1];

g[n]:=n;

g[n-1]:=n;

for i:=n-2 downto 1 do

if time[i+1]<=f[i+1] then g[i]:=i+1 else g[i]:=g[i+1];

ans:=0;

for i:=1 to m do

ans:=ans+time[b[i]]-t[i];

for ll:=1 to k do

begin

maxs:=0;

maxj:=0;

for i:=1 to m do

if ((sum[g[i]]-sum[i])>maxs) and (d[i]>0) then

begin

maxs:=sum[g[i]]-sum[i];

maxj:=i;

end;

l:=maxj;

r:=g[maxj];

if r>n-1 then r:=n-1;

dec(d[maxj]);

// writeln(ans);

ans:=ans-maxs;

for i:=l to r do

begin

time[i]:=max(f[i-1],time[i-1])+d[i-1];

end;

for i:=r downto l do

begin

if time[i+1]<=f[i+1] then

g[i]:=i+1

else

g[i]:=g[i+1];

end;

end;

writeln(ans);

end.