记录编号	32086	评测结果	AAAAAAAAAA
题目名称	垃圾陷阱	最终得分	100
用户昵称	Des.	是否通过	通过
代码语言	Pascal	运行时间	0.031 s
提交时间	2011-11-05 12:06:55	内存使用	0.27 MiB

program well;
uses math;
var f:array[-1000..4000]of longint;
    a,v,c:array[0..100]of longint;
    t,k,m,n,i,j:longint;
begin
assign(input,'well.in');
reset(input);
assign(output,'well.out');
rewrite(output);
readln(m,n);
for t:=1 to n do
  readln(a[t],v[t],c[t]);
for t:=1 to n-1 do
  for k:=1 to n-1 do
    if a[k]>a[k+1] then
      begin
        j:=a[k];a[k]:=a[k+1];a[k+1]:=j;
        j:=v[k];v[k]:=v[k+1];v[k+1]:=j;
        j:=c[k];c[k]:=c[k+1];c[k+1]:=j;
      end;
for j:=-1000 to n*30+1000 do
  f[j]:=-maxint;
f[10]:=0;
for i:=1 to n do
  begin
    for j:=0 to n*30-v[i] do
      f[j]:=f[j+a[i]-a[i-1]];
    for j:=n*30-v[i] downto 0 do
      begin
        f[j+v[i]]:=max(f[j+v[i]],f[j]);
        f[j]:=f[j]+c[i];
        if f[j]>=m then
          begin
            writeln(a[i]);
            close(output);
            halt;
          end;
      end;
  end;
j:=10;
for t:=1 to n do
  begin
    {j:=j-a[t]+a[t-1];
    if j<0 then
      begin
        j:=j+a[t]-1;
        break;
      end;
    if (t=n)and(j>=0) then
      begin
        j:=a[t]+j-1;
        break;
      end; }
    j:=j+v[t];
  end;
writeln(j);
close(output);
end.