//un fel de rucsac in 2 dimenisuni complexitate O(n^3)
#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++)
        {
            //pornim de la k-1 spre 1 pentru a nu lua un element de mai multe ori
            for(i = k-1; i >= 1; i--){
                for(int rest=0; rest < p; rest++){
                    //daca am ajuns in starea(i, rest) incercam sa 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";
    }

}