记录编号	80358	评测结果	AAAAAAAAAA
题目名称	垃圾陷阱	最终得分	100
用户昵称	C语言入门	是否通过	通过
代码语言	Pascal	运行时间	3.297 s
提交时间	2013-11-07 08:53:13	内存使用	27.26 MiB

program o;
var
d,g,i,jh,j,k,max:longint;
t,h,ff:array [0..101] of longint;
f:array [0..1,-1..3300,-1..4300] of boolean;
function min(a,b:longint):longint;
begin
 if a>b then min:=b
        else min:=a;
end;
begin
assign (input,'well.in');
assign (output,'well.out');
reset (input);
rewrite (output);
 read (d,g);
 for i:=1 to g do
  read (t[i],ff[i],h[i]);
 for i:=1 to g-1 do
  for j:=i+1 to g do
   if t[i]>t[j] then
    begin
    jh:=t[i];
    t[i]:=t[j];
    t[j]:=jh;
    jh:=ff[i];
    ff[i]:=ff[j];
    ff[j]:=jh;
    jh:=h[i];
    h[i]:=h[j];
    h[j]:=jh;
    end;
 fillchar(f,sizeof(f),false);
 f[0,0,10]:=true;
 for i:=0 to g+1 do
 begin
 fillchar(f[(i+1)mod 2],sizeof(f[(i+1)mod 2]),false);
  for j:=0 to d+100 do
   for k:=0 to (i+1)*30 do
    if f[i mod 2,j,k] then
     begin
      if j>=d then
       begin
        write (t[i-1]);
        close (input);
        close (output);
        halt;
       end;
      if t[i+1]-t[i]<=k then
       f[(i+1) mod 2,j+h[i],min(k-t[i+1]+t[i],3300)]:=true;
       if j+h[i]>=d then
        begin
         write (t[i]);
         close (input);
         close (output);
         halt;
        end;
      if t[i+1]-t[i]<=k+ff[i] then
       f[(i+1) mod 2,j,min(k+ff[i]-t[i+1]+t[i],3300)]:=true;
      if t[i]+k>max then max:=t[i]+k;
     end;
 end;
write (max);
close (input);
close (output);
end.