Pascal :

program defend;
const
  MAXN = 1010;
  MAXM = 10010;
type
  info = record
    v : array[0..MAXM+MAXN] of longint;//一横行
  end;
var
  n,m,pos,now : longint;
  num : array[0..MAXN] of longint;
  p : array[0..MAXN] of info;
  target,tmp : info;//target存目标函数式 tmp代换变量时用
procedure init;
var
  i,j,ql,qr,qk : longint;
begin
  read(n,m);
  for i := 1 to n do
  begin
    read(qk);
    p[i].v[0] := qk;
    num[i] := m+i;
  end;
  for i := 1 to m do
  begin
    read(ql,qr,qk);
    target.v[i] := qk;
    for j := ql to qr do
      p[j].v[i] := -1;
  end;
  inc(m,n);
end;
procedure pivot;
var
  i,j,k,minnum,key : longint;
begin
  minnum := maxlongint;
  pos := -1;
  for i := 1 to m do
    if target.v[i] > 0 then//每次在目标函数中找一个>0的数
    begin
      pos := i;
      break;
    end;
  if pos = -1 then
  begin
    writeln(target.v[0]);//找不到就结束算法
    close(input);
    close(output);
    halt;
  end;
  for i := 1 to n do
    if (p[i].v[pos] < 0) and (p[i].v[0] < minnum) then
    begin
      minnum := p[i].v[0];
      now := i;
    end;
  dec(p[now].v[num[now]]);
  inc(p[now].v[pos]);
  num[now] := pos;
  tmp := p[now];
  dec(tmp.v[pos]);

  key := target.v[pos];
  for k := 0 to m do
    inc(target.v[k],tmp.v[k]*key);
  for i := 1 to n do
  begin
    if p[i].v[pos] = 0 then continue;
    if i = now then continue;
    key := p[i].v[pos];
    for k := 0 to m do
      inc(p[i].v[k],tmp.v[k]*key);
  end;
end;
begin
  //assign(input,'defend.in');
  //assign(output,'defend.out');
  reset(input);
  rewrite(output);
  init;
  while true do pivot;
end.