{$I-,Q-,R-,S-}

  const
       FIN = 'tricouri.in';
       FOUT = 'tricouri.out';
       NMAX = 300000;
       PMAX = 20;
       KMAX = 5;

  var
      A : array[ 1..NMAX ] of longint;
      R, B : array[ 0..PMAX, 0..KMAX ] of longint;
      D : array[ 0..PMAX * KMAX, 0..PMAX, 0..KMAX ] of longint;
      i, j, N, M, x, y, pivot : longint;
      f, g : text;

 function MAX( a, b : longint ) : longint;
   begin
    if a > b then MAX := a else MAX := b;
   end;

  procedure dinamica( P : longint );
   var i, j, k, t, jj, rest, sum, min, poz, aux : longint;
   begin

    fillchar( R, sizeof( R ), 0 );
    for i := 1 to N do
          begin
            rest := A[i] mod P;
            if R[ rest, 0 ] < KMAX then
              begin
                   inc( R[ rest, 0 ] ); R[ rest, R[ rest, 0 ] ] := A[i];
              end else
                begin
                 min := R[ rest, 1 ]; poz := 1;
                 for j := 2 to KMAX do
                  if R[rest,j] < min then begin min := R[ rest, j ]; poz := j; end;
                  if A[i] > min then R[ rest, poz ] := A[i];
                 end;
           end;

   for i := 0 to P - 1 do
    for j := 1 to R[ i, 0 ] - 1 do
      for jj := j + 1 to R[ i, 0 ] do
        if R[ i, j ] < R[ i, jj ] then begin aux := R[ i, j ]; R[ i, j ] := R[ i, jj ];
                                             R[ i, jj ] := aux;
                                       end;
   for i := 0 to P * KMAX do
    for j := 0 to PMAX do
      for k := 0 to KMAX do D[ i, j, k ] := - 1;
    for i := 0 to P do D[0][i][0] := 0;
    for t := 1 to KMAX do
    for i := 0 to KMAX * P do
      for j := 1 to P do
        begin
         sum := 0; D[i][j][t] := D[i][j-1][t];
          for jj := 1 to R[j - 1,0] do
            begin
             sum := sum + R[ j - 1, jj ];
             if ( i - (j - 1) * jj >= 0 ) and ( t - jj >= 0 ) then
             if D[i - (j - 1) * jj ][ j - 1 ][ t - jj ] <> - 1 then
             D[i][j][t] := MAX( D[i][j][t], D[ i - (j-1) * jj ][ j - 1 ][ t - jj ] + sum );
            end;
         end;

    for j := 0 to P * KMAX do
      if j mod p = 0 then
        for i := 1 to KMAX do B[ p, i ] := MAX( B[p,i], D[ j, P, i ] );
  end;

  begin
    assign( f, FIN ); reset( f ); readln( f, N, M );
    assign( g, FOUT ); rewrite( g );
    for i := 1 to N do read( f, A[i] );
    for i := 0 to PMAX do
     for j := 0 to KMAX do B[ i, j ] := -1;

    for j := 2 to PMAX do dinamica( j );

    for  i := 1 to M do
     begin
      readln( f, x, y );
      writeln( g, B[y,x] );
     end;
     close( f );
     close( g );
    end.