#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;

ifstream fin("tricouri.in");
ofstream fout("tricouri.out");

const int MAXN = 300005;
const int MAXK = 6;
const int MAXP = 22;
int N, M;
int a[MAXN];
int D[MAXP][MAXK][MAXP];
int k, p;

void Read();
void Calc( int k );
void Answer();

int main()
{
    Read();

    memset(D, -1, sizeof(D));
    for ( int i = 1; i <= 20; i++ )
        Calc(i);

    Answer();

    fin.close();
    fout.close();
    return 0;
}

void Read()
{
    int i;

    fin >> N >> M;
    for ( i = 1; i <= N; i++ )
        fin >> a[i];
}

void Calc( int k )
{
    int ind, i, j;

  //  if ( k == 10 )
  //      cout << "DA";

    D[k][0][0] = 0;
    for ( ind = 1; ind <= N; ind++ )
    {
        for ( i = min(ind - 1, 5); i >= 1; i-- )
        {
            for ( j = 0; j < k; j++ )
                if ( D[k][i][j] != -1 )
                {
                 //   if ( k == 10 && a[ind] == 190 ) {
                 //       cout << i << ' ' << j << ' ' << ind << ' ' << D[k][i][j]; cin.get(); }

                    D[k][i + 1][(j + a[ind]) % k] = max( D[k][i + 1][(j + a[ind]) % k], D[k][i][j] + a[ind] );
                }
        }

        D[k][1][a[ind] % k] = max( D[k][1][a[ind] % k], a[ind] );
    }
}

void Answer()
{
    int i;

    for ( i = 1; i <= M; i++ )
    {
        fin >> k >> p;

        fout << D[p][k][0] << '\n';
    }
}