var
t,m,i,j:longint;
a,b,p:array[1..1000] of longint;
begin
read(t,m);
for i:=1 to m do
read(b[i],p[i]);
for i:=1 to m do
for j:=t downto b[i] do
if a[j]<a[j-b[i]]+p[i] then
a[j]:=a[j-b[i]]+p[i];
write(a[t]);
end.