#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[100005], st[100];
vector<int> d[25][25];
int frec[100];

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

void tipar(int x)
{
    int j;
    int aux = 0, sum = 0;
    for(j = 0; j<=20;j++)
    {
        frec[j] = 0;
    }
    for(j=1;j<=x;j++)
    {
        aux = (aux + st[j]) % p;
    }
    st[x + 1] = p - aux;
    if(st[x + 1] == p) return ;
    for(j=1;j<=x+1;j++)
    {
        if(frec[st[j]] < d[p][st[j]].size())
        {
             sum = sum + d[p][st[j]][frec[st[j]]];
            frec[st[j]]++;
        }
        else return;

    }
    for(j = 0; j<=20;j++)
    {
        frec[j] = 0;
    }
    sol = max(sol, sum);
    for(j=1;j<=x+1;j++)
    {
         //fout << st[j] <<" ";
    }
    //fout<<"\n";
    for(j=1;j<=x+1;j++)
    {
         //fout << d[p][st[j]][frec[st[j]]] <<" ";
         frec[st[j]]++;
    }
   // fout<<"\n";
    //fout << sum <<"\n";


}


inline void back(int vf)
{
    int i;
    if (vf== k) tipar(vf - 1);
    else
    for(i=st[vf-1];i<p;i++)
    {
        st[vf]=i;
        back(vf+1);

    }
}



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--)
    {
        fin >> k >> p;
        //fout<<p<<"\n";
        sol = -1;
        back(1);
        fout << sol << "\n";
    }

    for(i = 1; i <= n; i++)
    {
        //fout << a[i] <<" ";
    }
}