//https://www.infoarena.ro/problema/tricouri

#include<fstream>
#include<vector>
#include<string>
#include<algorithm>
#define modulo 666013

using namespace std;

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


string sir;
int i, n, k, j, sol, x, y, m, p;
int a[300005], st[100];
vector<int> d[25][25];
int dp[6][22];
int frec[100];
int v[105];

bool cmp(int x, int y)
{
    return x > y;
}


void clean() {

    for (int k = 0; k < 6; k++) {
        for (int p = 0; p < 22; p++) dp[k][p] = 0;
    }

}

int main()
{
    fin >> n >> m;
    for (i = 1; i <= n; i++)
    {
        fin >> a[i];
    }
    sort(a + 1, a + n + 1, cmp);
    for (i = 1; i <= n; i++)
    {
        for (j = 2; j <= 20;j++)
        {
            if (d[j][a[i] % j].size() < 5)
            {
                d[j][a[i] % j].push_back(a[i]);
            }

        }
    }



    while (m--)
    {
        //pentru fiecare query fac dp[i][j] = suma maxima avand i elemente care dau restul j la impartirea cu P;
        clean();
        fin >> k >> p;
        v[0] = 0;
        //iau doar elementele pe care le pot folosi pentru acest P
        for (int rest = 0; rest < p; rest++)
        {
            for (j = 0; j < d[p][rest].size();j++)
            {
                v[++v[0]] = d[p][rest][j];
            }
        }

        //imbunatatesc silutia folosing V[j]
        //fac un fel de rucsac pe doua dimensiuni
        for (j = 1; j <= v[0]; j++)
        {
            for (i = k - 1; i >= 1; i--) {
                for (int rest = 0; rest < p; rest++) {
                    //daca am ajuns in starea(i, rest) trecem in (i + 1, (rest + v[j] ) % p )
                    if (dp[i][rest] != 0)
                    {
                        dp[i + 1][(rest + v[j]) % p] = max(dp[i + 1][(rest + v[j]) % p], dp[i][rest] + v[j]);
                    }

                }
            }
            if (dp[1][v[j] % p] == 0)
            {
                //deoarece avem resturile in ordine descrescatoare este suficient sa modificam o singura data
                dp[1][v[j] % p] = v[j];
            }
        }
        if (dp[k][0] == 0)
        {
            fout << "-1\n";
        }
        else
            fout << dp[k][0] << "\n";
    }

}