Program medic;

Var
panduan:array [1..100] of boolean;
a:array [0..100] of integer;
s:array [1..100,1..2] of integer;
time,temp,m,n,j,i,jiazhi:integer;
f1,f2:text;

procedure try(i:integer);
var jiazhi1,k,j:integer;
begin
 for k:=a[i-1]+1 to n do begin
  if panduan[k] then begin
   a[i]:=k;
   panduan[k]:=false;
   if i=m then begin
    temp:=0; jiazhi1:=0;
    for j:=1 to m do
     temp:=temp+s[a[j],1];
    if temp<=time then begin
     for j:=1 to m do
      jiazhi1:=jiazhi1+s[a[j],2];
     if jiazhi1>jiazhi then
      jiazhi:=jiazhi1;
    end;
   end
   else try(i+1);
   panduan[k]:=true;
  end;
 end;
end;

Begin
assign(f1,'medic.in');
assign(f2,'medic.out');
reset(f1);
rewrite(f2);
read(f1,time,n);
readln(f1);
for i:=1 to n do
 for j:=1 to 2 do
  read(f1,s[i,j]);
for j:=1 to n do panduan[j]:=true;
for m:=1 to n do begin
 a[0]:=0;
 try(1);
end;
write(f2,jiazhi);
close(f1);
close(f2);
End.