var
  a:array[2..20,0..19,1..5] of longint;
  query:array[1..100,1..3] of longint;
  sol:array[2..20,1..5] of longint;
  cat,done:array[0..20] of longint;
  g,i,j,k,n,m,p:longint;
  t:array[0..5] of longint;

procedure baga(x:longint);
var i:longint;
begin
  for i:=5 downto x+1 do
    a[p,k,i]:=a[p,k,i-1];
  a[p,k,x]:=j;
end;

procedure verif;
var gol,i,max:longint;
  b:boolean;
begin
  fillchar(cat,sizeof(cat),0);
  max:=0; gol:=0;
  b:=true;
  for i:=1 to 5 do
    if t[i]>-1 then
    begin
      inc(cat[t[i]]);
      if a[p,t[i],cat[t[i]]]>0
        then max:=max+a[p,t[i],cat[t[i]]]
        else b:=false;

    end
    else inc(gol);
  if gol=5 then b:=false;
  if (b) and (max mod p=0) and (max>sol[p,5-gol]) then sol[p,5-gol]:=max;

end;

procedure back(x:longint);
var i:longint;
begin
  if x>5 then
  begin
    verif;
    exit;
  end;
  for i:=t[x-1] to p-1 do
  begin
    t[x]:=i;
    back(x+1);
    t[x]:=0;
  end;
end;

begin
  assign(input,'tricouri.in');
  reset(input);
  readln(n,m);
  for i:=1 to n do
  begin
    read(j);
    for p:=2 to 20 do
    begin
      k:=j mod p;
      g:=1;
      while (g<=5)and(a[p,k,g]>=j) do inc(g);
      if g<=5 then baga(g);
    end;
  end;
  for i:=2 to 20 do
    for j:=1 to 5 do sol[i,j]:=-1;


  assign(output,'tricouri.out');
  rewrite(output);
  t[0]:=-1;
  for i:=1 to m do
  begin
    readln(k,p);
    if done[p]=0 then
    begin
      back(1);
      done[p]:=1;
    end;
    writeln(sol[p,k]);
  end;
  close(output);
end.