{$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;


 procedure poz( lo, hi : longint ); inline;
  var i, j, di, dj, aux : longint;
   begin
    i := lo; j := hi; di := 0; dj := - 1;
     while i < j do
       begin
        if A[i] < A[j] then begin aux := A[i]; A[i] := A[j]; A[j] := aux;
                                  aux := di; di := - dj; dj := - aux;
                            end;
        inc( i, di ); inc( j, dj );
       end;
    pivot := i;
   end;

  procedure quick( lo, hi : longint ); inline;
   begin
    if lo < hi then
      begin
       poz( lo, hi );
       quick( lo, pivot - 1 );
       quick( pivot + 1, hi );
      end;
   end;

  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 : 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;
           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] );
    quick( 1, N );
    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.