记录编号	27955	评测结果	AAAAAAAAAA
题目名称	垃圾陷阱	最终得分	100
用户昵称	feng	是否通过	通过
代码语言	Pascal	运行时间	0.004 s
提交时间	2011-10-10 20:22:01	内存使用	0.16 MiB

var ansl,n,m,i,j,c:longint;
      t,l,h:Array[0..105]of longint;
      a:Array[0..100,0..100]of longint;
  procedure print(ans:longint);
  begin
  assign(output,'well.out');rewrite(output);
   writeln(ans);
  close(output);
   halt;
  end;
  function max(x,y:longint):longint;
  begin
    if x>y then max:=x else max:=y;
  end;
  begin
    assign(input,'well.in');reset(input);
    readln(m,n);
    for i:=1 to n do readln(t[i],l[i],h[i]);t[0]:=0;
    close(input);
     for i:=1 to n do
      for j:=i+1 to n do
        if t[i]>t[j] then begin
                            c:=t[i];t[i]:=t[j];t[j]:=c;
                            c:=l[i];l[i]:=l[j];l[j]:=c;
                            c:=h[i];h[i]:=h[j];h[j]:=c;
                          end;
    for i:=0 to n do
      for j:=0 to m do
        a[i,j]:=-maxlongint;
    a[0,0]:=10;
    ansl:=0;
    for i:=1 to n do
      for j:=0 to m do
        begin
        if a[i-1,j]>=t[i]-t[i-1] then a[i,j]:=a[i-1,j]+l[i]-t[i]+t[i-1];
        if (j-h[i]>=0)and(a[i-1,j-h[i]]>=t[i]-t[i-1]) then a[i,j]:=max(a[i,j],a[i-1,j-h[i]]-t[i]+t[i-1]);
        if (j=m)and(a[i,m]<>-maxlongint) then print(t[i]);
        if a[i,j]+t[i]>ansl then ansl:=a[i,j]+t[i];
    end;
    print(ansl);
  end.