program poj2063;//By_Thispoet
Const
  maxn=100000;
Var
  i,j,k,m,n,p,t                 :Longint;
  f                             :Array[0..maxn]of Longint;
  a,b                           :Array[1..10]of Longint;

Function Max(i,j:Longint):Longint;
begin
  if i>j then exit(i);exit(j);
end;


begin

  readln(t);
  while t>0 do
    begin
      readln(m,k);
      readln(n);
      for i:=1 to n do
        begin
          readln(a[i],b[i]);
          a[i]:=a[i] div 1000;
        end;
      repeat
        p:=m div  1000;
        fillchar(f,sizeof(f),0);
        for i:=1 to n do
          for j:=0 to p-a[i] do
            f[j+a[i]]:=Max(f[j]+b[i],f[j+a[i]]);
        dec(k);
        inc(m,f[p]);
      until k<=0;
      writeln(m);
      dec(t);
    end;

end.