记录编号	80026	评测结果	AAAAAAAAAA
题目名称	垃圾陷阱	最终得分	100
用户昵称	,	是否通过	通过
代码语言	Pascal	运行时间	0.014 s
提交时间	2013-11-06 17:57:13	内存使用	1.37 MiB

program gmy(input,output);
var
 a,b,c:array[0..1000]of longint;
 i,j,k,l,d,n,bb:longint;
 f:array[0..100,-100..3000]of longint;
procedure sort(l,r:longint);
var
 i,j,x,y:longint;
begin
 i:=l; j:=r; x:=a[(l+r) div 2];
 repeat
   while a[i]<x do inc(i);
   while x<a[j] do dec(j);
   if not(i>j) then begin
                     y:=a[i];
                     a[i]:=a[j];
                     a[j]:=y;
                     y:=b[i];
                     b[i]:=b[j];
                     b[j]:=y;
                     y:=c[i];
                     c[i]:=c[j];
                     c[j]:=y;
                     inc(i);
                     j:=j-1;
                    end;
 until i>j;
 if l<j then sort(l,j);
 if i<r then sort(i,r);
end;
function max(a,b:longint):longint;
begin
 if a>b then exit(a)
        else exit(b);
end;
begin
 assign(input,'well.in');
 reset(input);
 assign(output,'well.out');
 rewrite(output);
 readln(d,n);
 for i:=1 to n do
   readln(a[i],b[i],c[i]);
 sort(1,n);
 l:=10; bb:=10; a[0]:=1; a[n+1]:=9999999;
 fillchar(f,sizeof(f),128);
 f[0,10]:=0;
 for i:=1 to n do
   begin
    bb:=bb+a[i-1]-a[i];
    l:=l+b[i];
    if bb<0 then begin
                  writeln(a[i-1]+bb);
                  close(input);
                  close(output);
                  halt;
                 end;
    for j:=a[i] to l do
      begin
       f[i,j]:=f[i-1,j]+c[i];
       if j-b[i]>=a[i]
       then f[i,j]:=max(f[i,j],f[i-1,j-b[i]]);
       if f[i,j]>=d then begin
                          writeln(a[i]);
                          close(input);
                          close(output);
                          halt;
                         end;
      end;
    bb:=bb+b[i];
   end;
 writeln(a[i]+bb-1);
 close(input);
 close(output);
end.