var n,i,s,max,nr,p:longint;
    m,k:byte;
    f,g:text;
    a:array [1..300000] of longint;
    c:array [1..300000] of byte;
    ok:boolean;
procedure citire;
begin
read(f,n,m);
readln(f);
for i:=1 to n do read(f,a[i]);
readln(f);
end;
begin
assign(f,'tricouri.in'); reset(f);
assign(g,'tricouri.out'); rewrite(g);
citire;
for i:=1 to m do begin
  read(f,k,p);
  readln(f);
  ok:=true;
  max:=0;
  while ok do begin
    i:=n;
    while (c[i]=1) and (i>0) do begin
      c[i]:=0;
      i:=i-1;
    end;
    if i=0 then ok:=false
           else begin
             c[i]:=1;
             nr:=0; s:=0;
             for i:=1 to n do begin
               if c[i]=1 then begin
                 s:=s+a[i];
                 nr:=nr+1;
               end;
             end;
             if (s mod p=0) and (k=nr) and  (s>max) then max:=s;
           end;
  end;
  if max<>0 then write(g,max)
            else write(g,-1);
  writeln(g);
end;
close(g);
end.