const
  lim=300000;
  base=20;
var
  a:array[0..19,0..5,0..lim] of longint;
  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 n do
        a[i,j,r]:=-1;
  for i:=1 to n do
  begin
    read(tric[i]);
    a[0,0,i]:=0;
  end;
  a[0,0,0]:=0;
  for i:=1 to n do
  begin
    for r:=0 to 19 do
      for j:=0 to 4 do
        if a[r,j,i-1]>=0 then
        begin
          if a[(r+tric[i]) mod base,j+1,i]<a[r,j,i-1]+tric[i] then
            a[(r+tric[i]) mod base,j+1,i]:=a[r,j,i-1]+tric[i];
        end;
    for r:=0 to 19 do
      for j:=0 to 5 do
        if a[r,j,i-1]>a[r,j,i] then a[r,j,i]:=a[r,j,i-1];
  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,n]>a[r,i,n] then a[r,i,n]:=a[j,i,n];
        j:=j+r;
      end;
      if (j=20) and (a[0,i,n]>a[r,i,n]) then a[r,i,n]:=a[0,i,n];
    end;
  for r:=1 to m do
  begin
    readln(i,j);
    writeln(a[j,i,n]);
  end;
  close(input);
  close(output);
end.