var
i,j,m,n:integer；
v,p:array[0..30] of longint；
f:array[0..30,-2..30000] of longint；
begin
fillchar(v,sizeof(v),0)；
fillchar(p,sizeof(p),0)；
fillchar(f,sizeof(f),0)；
readln(n,m)；
for i:=1 to m do begin
read(v[i],p[i])；
p[i]:=p[i]*v[i]；
end；
for i:=1 to m do
for j:=1 to n do begin
f[i,j]:=f[i-1,j]；
if (v[i]<=j)and(f[i-1,j]<f[i-1,j-v[i]]+p[i]) then
f[i,j]:=f[i-1,j-v[i]]+p[i]；
end；
writeln(f[m,n])；
end.
var
i,j,m,n:integer；
v,p:array[0..30] of longint；
f:array[0..30,-2..30000] of longint；
begin
fillchar(v,sizeof(v),0)；
fillchar(p,sizeof(p),0)；
fillchar(f,sizeof(f),0)；
readln(n,m)；
for i:=1 to m do begin
read(v[i],p[i])；
p[i]:=p[i]*v[i]；
end；
for i:=1 to m do
for j:=1 to n do begin
f[i,j]:=f[i-1,j]；
if (v[i]<=j)and(f[i-1,j]<f[i-1,j-v[i]]+p[i]) then
f[i,j]:=f[i-1,j-v[i]]+p[i]；
end；
writeln(f[m,n])；
end.
var
i,j,m,n:integer;
v,p:array[0..30] of longint;
f:array[0..30,-2..30000] of longint;
begin
fillchar(v,sizeof(v),0);
fillchar(p,sizeof(p),0);
fillchar(f,sizeof(f),0);
readln(n,m);
for i:=1 to m do begin
read(v[i],p[i]);
p[i]:=p[i]*v[i];
end;
for i:=1 to m do
for j:=1 to n do begin
f[i,j]:=f[i-1,j];
if (v[i]<=j)and(f[i-1,j]<f[i-1,j-v[i]]+p[i]) then
f[i,j]:=f[i-1,j-v[i]]+p[i];
end;
writeln(f[m,n]);
end.
var
i,j,m,n:integer；
v,p:array[0..30] of longint；
f:array[0..30,-2..30000] of longint；
begin
fillchar(v,sizeof(v),0)；
fillchar(p,sizeof(p),0)；
fillchar(f,sizeof(f),0)；
readln(n,m)；
for i:=1 to m do begin
read(v[i],p[i])；
p[i]:=p[i]*v[i]；
end；
for i:=1 to m do
for j:=1 to n do begin
f[i,j]:=f[i-1,j]；
if (v[i]<=j)and(f[i-1,j]<f[i-1,j-v[i]]+p[i]) then
f[i,j]:=f[i-1,j-v[i]]+p[i]；
end；
writeln(f[m,n])；
end.