program ex(f1,f2);
type
 zn=array [1..1000] of integer;
 ma=array [0..1000] of integer;
var
 b,v:zn;
 a:ma;
 i,j,k,m,t,n:longint;
 f1,f2:text;
begin
 assign(f1,'medic.in'); reset(f1);
 assign(f2,'medic.out'); rewrite(f2);
 readln(f1,t,m);
 for i:=1 to m do
  readln(f1,b[i],v[i]);
 for i:=1 to m do a[i]:=0;
  a[0]:=1;
 for i:=1 to m do
 for j:=t downto b[i] do
   if (a[j-b[i]]>0) and (a[j]<a[j-b[i]]+v[i]) then
    a[j]:=a[j-b[i]]+v[i];
 n:=0;
 for i:=1 to t do
  if a[i]>n then n:=a[i];
 dec(n);
 writeln(f2,n);
 close(f1);
 close(f2);
end.