RT

count 表示 第i种面额在f[j] 放的数量

Program P1276;
const
   maxn=20;
   maxcash=1000000;
var
   cash,n,i,j:longint;
   cost,d:array[1..maxn] of longint;
   f,count:array[0..maxcash] of longint;
begin
   while not seekeof do
   begin
      read(cash,n);
      for i:=1 to n do read(d[i],cost[i]);
      fillchar(f,sizeof(f),0);
      for i:=1 to n do
      begin
         fillchar(count,sizeof(count),0);
         for j:=cost[i] to cash do
         begin
            if (f[j]<f[j-cost[i]]+cost[i]) and (count[j-cost[i]]<d[i]) then
            begin
               f[j]:=f[j-cost[i]]+cost[i];
               count[j]:=count[j-cost[i]]+1;
            end;
         end;
      end;

      writeln(f[cash]);
   end;
end.