program medic;
var
  t, n, j, max, now, rep: longint;
  w, v: array [1..100] of longint;
  fin,fout:text;

procedure search(p:byte);
var
  i: longint;
begin
  if p>n then
  begin
    if now>max then
      max:=now;
    exit;
  end;
  if rep>=w[p] then
  begin
    rep:=rep-w[p];
    now:=now+v[p];
    search(p+1);
    now:=now-v[p];
    rep:=rep+w[p];
  end;
  search(p+1);
end;

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

  readln(fin,t,n);
  now:=0;
  max:=0;
  rep:=t;
  for j:=1 to n do
    readln(fin,w[j], v[j]);
  search(1);
  writeln(fout,max);

  close(fin);
  close(fout);
end.