program sdf;
    var v,x:array[1..3000] of integer;
        n,k,i,z,j,t,max,nr,s,m,p:longint;
        f,g:text;
begin

     assign(f,'tricouri.in');reset(f);
     assign(g,'tricouri.out');rewrite(g);
     readln(f,n,m);
     z:=1;
     for i:=1 to n do z:=z*2;
     z:=z-1;
     for i:=1 to n do read(f,x[i]);
     for t:=1 to m do begin
         readln(f,k,p);
         for j:=1 to n do v[i]:=0;
         max:=-1;
         for j:=1 to z do begin
             i:=n;
             while v[i]=1 do begin
                   v[i]:=0;
                   i:=i-1;
                                end;
             v[i]:=1;
             nr:=0;s:=0;
             for i:=1 to n do
                 if v[i]=1 then begin
                    s:=s+x[i];
                    nr:=nr+1;
                             end;
             if (nr=k)and(s mod p=0) then
                if s>max then max:=s;
                         end;
         writeln(g,max);
                        end;
     close(g);
     close(f);
end.