program tricouri;
var x,n,i,j,l,o,r,m,k,p,rez:integer;
a:array [1..10000] of longint;
s:longint;
f,g:text;
begin
  assign(f,'tricouri.in'); assign(g,'tricouri.out');
  reset(f); rewrite(g);
  read(f,n,m);
  for i:=1 to n do read(f,a[i]);
  x:=0;
  repeat
    x:=x+1;
    read(f,k,p);
    if k=1 then
      begin
        rez:=0;
        for i:=1 to n do
          if (a[i] mod p=0) and (a[i]>rez) then rez:=a[i];
        if rez=0 then writeln (g,'-1') else writeln(rez);
      end
    else if k=2 then
      begin
        rez:=-1;
        for i:=1 to n-1 do
          for j:=i+1 to n do
            if ((a[i]+a[j]) mod p=0) and ((a[i]+a[j])>rez) then rez:=a[i]+a[j];
         writeln(g,rez);
      end
    else if k=3 then
      begin
      rez:=-1;
      for i:=1 to n-2 do
        for j:=i+1 to n-1 do
          for l:=j+1 to n do
            if ((a[i]+a[j]+a[l]) mod p=0) and ((a[i]+a[j]+a[l])>rez) then rez:=a[i]+a[j]+a[l];
      writeln(g,rez);
      end
    else if k=4 then
      if n<4 then writeln(g,'-1')
        else
        begin
        rez:=-1;
         for i:=1 to n-3 do
          for j:=i+1 to n-2 do
           for l:=j+1 to n-1 do
            for o:=l+1 to n do
          if (a[i]+a[j]+a[l]+a[o]>rez) and ((a[i]+a[j]+a[l]+a[o]) mod p=0) then
            rez:=a[i]+a[j]+a[l]+a[o];
         writeln(g,rez);
         end
      else if n<5 then writeln(g,'-1')
      else begin
      rez:=-1;
         for i:=1 to n-4 do
          for j:=i+1 to n-3 do
           for l:=j+1 to n-2 do
            for o:=l+1 to n-1 do
             for r:=o+1 to n do
          if (a[i]+a[j]+a[l]+a[o]+a[r]>rez) and ((a[i]+a[j]+a[l]+a[o]+a[r]) mod p=0) then
            rez:=a[i]+a[j]+a[l]+a[o]+a[r];
         writeln(g,rez);
         end;
  until (x=m);
  close(f); close(g);
end.