type long=longint;

var g:array[0..100,0..30000] of long;

p,v:array[1..100] of long;

i,j,n,m:long;

begin

fillchar(g,sizeof(g),0);

readln(n,m);

for i:=1 to m do

begin

readln(p[i],v[i]);

end;

for i:=1 to m do

for j:=1 to n do

if (j>=p[i]) and (g[i-1,j-p[i]]+v[i]>g[i-1,j]) then

g[i,j]:=g[i-1,j-p[i]]+v[i]

else

g[i,j]:=g[i-1,j];

writeln(g[m,n]);

end.