记录编号	132626	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]借教室	最终得分	100
用户昵称	传奇	是否通过	通过
代码语言	Pascal	运行时间	2.312 s
提交时间	2014-10-26 12:06:33	内存使用	19.24 MiB

program cojs1266;
var
  room,d,s,t,sum:array[0..1000000] of longint;
  n,m,l,r,now,k,ssum,i:longint;
  f:boolean;
begin
  assign(input,'classrooms.in');
  assign(output,'classrooms.out');
  reset(input);
  rewrite(output);

  readln(n,m);
  for i:=1 to n do
    read(room[i]);
  for i:=1 to m do
    readln(d[i],s[i],t[i]);
  now:=0;
  l:=0; r:=m+1;
  while l<>r do
    begin
      f:=true;
      k:=(l+r) div 2;
      if k>now then
        for i:=now+1 to k do
          begin
            sum[s[i]]:=sum[s[i]]+d[i];
            sum[t[i]+1]:=sum[t[i]+1]-d[i];
          end
      else
        for i:=k+1 to now do
          begin
            sum[s[i]]:=sum[s[i]]-d[i];
            sum[t[i]+1]:=sum[t[i]+1]+d[i];
          end;
      now:=k;
      ssum:=0;
      for i:=1 to n do
        begin
          inc(ssum,sum[i]);
          if ssum>room[i] then
            begin
              f:=false;
              break;
            end;
        end;
      if f then l:=k+1
      else
        r:=k;
    end;
  if (k=m)and(f) then
    writeln(0)
  else
    begin
      writeln(-1);
      writeln(l);
    end;

  close(input);
  close(output);
end.