program cch(input,output,f1,f2);
var
 f1,f2:text;
 a:array[0..1000]of longint;
 w,c:array[0..100] of longint;
 b:array[0..100,0..100] of boolean;
 i,m,t,max,j,q,p:longint;

{function solve(k:integer):longint;
var
 i:integer;
begin
 max:=0;
 if k=0 then solve:=0
        else for i:=1 to m do begin
          if k>=w[i] then
           if solve(k-w[i])+c[i]>max then  max:=solve(k-w[i])+c[i];
         end;
 solve:=max;
end;
}
begin
 assign(f1,'medic.in');
 assign(f2,'medic.out');
 reset(f1);
 rewrite(f2);
 readln(f1,t,m);
 for i:=1 to m do readln(f1,w[i],c[i]);
 a[0]:=0;
 fillchar(b,sizeof (b),true);
 for i:=1 to t do begin
  max:=0;
  for j:=1 to m do
   if (i>=w[j])and b[i-1,j] then
    if (a[i-w[j]]+c[j])>max then begin
      max:=a[i-w[j]]+c[j];
      q:=j; p:=i-w[j];
     end;
  for j:=1 to m do b[i,j]:=b[p,j];
  b[i,q]:=false;
  if max=0 then a[i]:=a[i-1]
           else a[i]:=max;
 end;
 writeln(f2,a[t]);
 close(f1);
 close(f2);
end.