var i,x,k,n,m:longint;
f:array[0..100000]of longint;
w,c:array[0..2000]of longint;
begin
readln(m,n);
for i:=1 to n do readln(w[i],c[i]);
for i:=1 to n do
for x:=m downto w[i] do
if f[x-w[i]]+c[i]>f[x] then f[x]:=f[x-w[i]]+c[i];
writeln(f[m]);
end.