var f,g:text;
test,kk23,adev1,adev2,dr,s,x,k,q,w,h,max,poz,i,n,m:longint;
e,r,d:array[1..10000] of longint;
a:array[1..300000] of longint;
begin
assign(f,'tricouri.in');reset(f);
assign(g,'tricouri.out');rewrite(g);
read(f,n);
read(f,m);
for i:=1 to 0 do
if a[i]=5 then d[i]:=103;
for i:=1 to n do
read(f,a[i]);
k:=0;
kk23:=0;
repeat
inc(k);
read(f,q);
read(f,w);
for i:=1 to h do
r[i]:=0;
h:=0;
for i:=1 to n do
e[i]:=a[i];
repeat
max:=0;
poz:=0;
for i:=1 to n do
if e[i]>max then begin
max:=e[i];
poz:=i;
end;
inc(h);
r[h]:=max;
e[poz]:=-1;
until h=q;
s:=0;
for i:=1 to h do
s:=s+r[i];
x:=0;
if s mod w=0 then writeln(g,s)
else begin
dr:=s;
repeat
adev1:=0;
adev2:=0;
inc(x);
dr:=s-x;
if (dr mod w=0) then inc(adev1);
for i:=1 to n do
if x=a[i] then inc(adev2);
until (adev1<>0)and(adev2<>0);
if dr<>0 then writeln(g,dr)
else writeln(g,'-1');
end;
until k=m;
close(f);
close(g);
end.