program happy;
var
  w:array[1..25] of longint;
  v:array[1..25] of longint;
  x:array[1..25] of longint;
  i,j,n,m,nn:longint;
  ss,s:longint;
  fin,fout:text;

procedure init;
begin
  readln(fin,n,m);
  for i:=1 to m do
  begin
    readln(fin,w[i],v[i]);
    x[i]:=0;
  end;
  s:=0;
  ss:=0;
end;

procedure print;
begin
  writeln(fout,s);
  close(fin);
  close(fout);
end;

procedure search(t:longint);
var
  k:longint;
begin
  k:=0;
  repeat
    inc(k);
    if (x[k]=0) and (nn>w[k]) then
    begin
      nn:=nn-w[k];
      x[k]:=1;
      ss:=ss+v[k]*w[k];
      if (nn=0) or (t=m) or (k=m) then
      begin
        if ss>s then s:=ss
        else search(t+1);
      end
      else search(t+1);
      nn:=nn+w[k];
      x[k]:=0;
      ss:=ss-v[k]*w[k];
    end;
  until k=m;
end;

begin
  assign(fin,'happy.in');
  reset(fin);
  assign(fout,'happy.out');
  rewrite(fout);

  init;
  nn:=n;
  search(1);
  print;

end.