#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 == 3 )
  //      cout << "DA";

    D[k][0][0] = 0;
    for ( ind = 1; ind <= N; ind++ )
    {
        for ( i = 5; i >= 1; i-- )
        {
            for ( j = 0; j < k; j++ )
                if ( D[k][i][j] != -1 )
                    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][ind % k], a[ind] );
    }
}

void Answer()
{
    int i;

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

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