program happy;
var 
  i,j,k,n,m:longint;
  d,p,v:array[0..26]of longint;
  c:array[0..30002,0..26]of longint;
begin
  readln(n,m);
  for i:=1 to m do begin
    readln(v[i],p[i]); d[i]:=v[i]*p[i];
  end;
  for i:=1 to n do begin
    for j:=1 to m do begin
      c[i,j]:=c[i,j-1];
      if i>=v[j] then
        if c[i,j]<c[i-v[j],j-1]+d[j] then
          c[i,j]:=c[i-v[j],j-1]+d[j];
    end;
  end;
  writeln(c[n,m]);
end.


/**************************************************************
	Problem: 2261
	User: admin
	Language: Pascal
	Result: Wrong Answer
****************************************************************/