const
  lim=300000;
  base=20;
var
  a:array[0..19,0..5,0..1] of longint;
  p,c,i,j,r,n,m:longint;
  tric:array[1..lim] of longint;

begin
  assign(input,'tricouri.in');
  reset(input);
  assign(output,'tricouri.out');
  rewrite(output);
  readln(n,m);
  for i:=0 to 19 do
    for j:=0 to 5 do
      for r:=0 to 1 do
        a[i,j,r]:=-1;
  for i:=1 to n do
    read(tric[i]);
  a[0,0,0]:=0;
  p:=0; c:=1;
  for i:=1 to n do
  begin
    for r:=0 to 19 do
      for j:=0 to 4 do
        if a[r,j,p]>=0 then
        begin
          if a[(r+tric[i]) mod base,j+1,c]<a[r,j,p]+tric[i] then
            a[(r+tric[i]) mod base,j+1,c]:=a[r,j,p]+tric[i];
        end;
    for r:=0 to 19 do
      for j:=0 to 5 do
        if a[r,j,p]>a[r,j,c] then a[r,j,c]:=a[r,j,p];
    p:=1-p;
    c:=1-c;
  end;
  for r:=2 to 10 do
    for i:=0 to 5 do
    begin
      j:=r*2;
      while j<20 do
      begin
        if a[j,i,p]>a[r,i,p] then a[r,i,p]:=a[j,i,p];
        j:=j+r;
      end;
      if (j=20) and (a[0,i,p]>a[r,i,p]) then a[r,i,p]:=a[0,i,p];
    end;
  for r:=1 to m do
  begin
    readln(i,j);
    writeln(a[j,i,p]);
  end;
  close(input);
  close(output);
end.