program medic;
  var
    t,m,c,ans:integer;
    a:array[1..2,1..100]of integer;
    b:array[1..100]of boolean;
    f1,f2:text;
    procedure ini;
      var
        i,j:integer;
      begin
        assign(f1,'medic.in');reset(f1);
        assign(f2,'medic.out');rewrite(f2);
        readln(f1,t,m);
        for i:=1 to m do begin
          for j:=2 downto 1 do read(f1,a[j,i]);
          readln(f1);
        end;
        close(f1);
      end;
    procedure try(t:integer);
      var
        i,j:integer;
        f:boolean;
      begin
        for i:=1 to m do
          if b[i]and(t-a[2,i]>=0)then
            begin
              inc(c,a[1,i]);
              b[i]:=false;
              j:=1;f:=true;
              while f and(j<=m)do
               if b[j] and (t-a[2,i]-a[2,j]>=0) then f:=false
                else inc(j);
              if f and(ans<c) then ans:=c
              else try(t-a[2,i]);
              b[i]:=true;
              dec(c,a[1,i]);
            end;
      end;
  begin
    ini;
    ans:=0;
    fillchar(b,sizeof(b),true);
    try(t);
    write(f2,ans);
    close(f2);
  end.