var s:array[0..5000000] of byte;
    a:array[1..300001] of longint;
    ok:longint;
    ok1:boolean;
    max1,max,n,m,i,j,x,k,p:longint;
    f,g:text;
begin
 assign(f,'tricouri.in'); reset(f);
 assign(g,'tricouri.out'); rewrite(g);
 read(f,n,m);
 s[0]:=0;
 max:=0;
 for i:=1 to n do begin
  read(f,x);
  ok:=1;
  for j:=1 to max do
   if (a[j]>=x) and (a[j+1]<=x) then
     ok:=j+1;
  max:=max+1;
  for j:=max downto ok+1 do
   a[j]:=a[j-1];
  a[ok]:=x;
 end;
 max1:=0;
 for i:=1 to max do
  for j:=max1 downto 0 do
   if ((s[j]<>0) or (j=0)) and (s[j+a[i]]=0) and (s[j]<>5)then
    begin
     x:=j+a[i];
     s[x]:=s[j]+1;
     if j+a[i]>max1 then
      max1:=j+a[i];
    end;
 for i:=1 to m do begin
  read(f,k,p); ok1:=true;
  for j:=max1 div p downto 1 do
   if s[j*p]=k then begin
    writeln(g,j*p);
    ok1:=false;
    break;
   end;
  if ok1 then
   writeln(g,'-1')
 end;
 close(f); close(g);
end.