{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S+,T-,V+,X+,Y+}
{$M 16384,65520,655360}
const
      fi                        ='sieuthi.inp';
      fo                        ='sieuthi.out';
      maxn                      = 500;
      maxs                      = 20000;
type matrix                     = array[0..maxs] of integer;
var
   fh                           : text;
   f1                           : matrix;
   f2                           : ^matrix;
   n, s                         : longint;
   C, M                         : array[0..maxn] of integer;
procedure input;
var
   i, j: longint;

  begin
    assign(fh, fi); reset(fh);
    readln(fh, s, n);
    for i:=1 to n do
      readln(fh, c[i], m[i]);
    close(fh);
  end;
function min(a, b: longint): longint;
  begin
    if a> b then min:= b
            else min:= a;
  end;

procedure qhd;
var
   i, j, k, tong: longint;
  begin
    new(f2);
    fillchar(f1, sizeof(f1), 0);
    fillchar(f2^, sizeof(f2^), 0);
    f1[0]:= 1;
    for i:=1 to n do
      begin
        f2^:= f1;
        fillchar(f1, sizeof(f1), 0);
        for j:=s downto 0 do
         begin
           tong:= 0;
           for k:= min(m[i], j div c[i]) downto 1 do
             tong:= tong+ f2^[j- k* c[i]];
           f1[j]:= tong + f2^[j];
         end;
      end;
    dispose(f2);
  end;
procedure truyvet;
var chon: array[1..maxn] of longint;
procedure inkq;
var i: longint;
  begin
    assign(fh, fo); rewrite(fh);
    writeln(fh, f1[s]);
    for i:=1 to n do
      write(fh, chon[i],' ');
    close(fh);
    halt;
  end;
procedure try(i: longint; tong: longint);
var j: longint;
  begin
    if i> n then     
if t />       else
    else
      for j:=0 to min(m[i], tong div c[i]) do
        begin
          chon[i]:= j;
          try(i+1, tong- j*c[i]);
        end;
  end;
begin
  try(1,s);
  {chi xay ra neu khong tim thay ket qua}
  assign(fh, fo); rewrite(fh);
  writeln(fh, f1[s]);
  writeln(fh,'Khong tim thay phuong an thoa man');

  close(fh);
end;
begin
     input;
     qhd;
     truyvet;
end.
HAY THÌ VOTE SAO CKO MIK NHA :>