#include<fstream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstdlib>
#define LG 1500000
using namespace std;
int n,m,K,P;
vector <int> G[21][21],v;
int best[2][6][21],ind;
char buffer[LG];

inline void Citeste(int &x)
{
    while(buffer[ind]<'0' || '9'<buffer[ind])
    {
        ind++;
        if(ind==LG)
        {
            fread(buffer,1,LG,stdin);
            ind=0;
        }
    }
    x=0;
    while('0'<=buffer[ind] && buffer[ind]<='9')
    {
        x=x*10+buffer[ind]-'0';
        ind++;
        if(ind==LG)
        {
            fread(buffer,1,LG,stdin);
            ind=0;
        }
    }
}

int main()
{
    int i,j,x,r,p;
    vector <int>::iterator it;

    freopen("tricouri.in","r",stdin);
    fread(buffer,1,LG,stdin);

    Citeste(n); Citeste(m);
    for(j=2;j<=20;j++)
        for(r=0;r<j;r++)
            for(i=0;i<=5;i++)
                G[j][r].push_back(0);
    for(i=1;i<=n;i++)
    {
        Citeste(x);
        for(j=2;j<=20;j++)
        {
            r=x%j;
            if(x>G[j][r][5])
                G[j][r][5]=x;
            p=4;
            while(p>=0 && G[j][r][p]<G[j][r][p+1])
            {
                swap(G[j][r][p],G[j][r][p+1]);
                p--;
            }
        }
    }
    ofstream fout("tricouri.out");
    while(m--)
    {
        Citeste(K); Citeste(P);
        for(i=0;i<P;i++)
            for(it=G[P][i].begin();it!=G[P][i].end();it++)
                if(*it)
                    v.push_back(*it);
        for(i=0;i<=K;i++)
            for(j=0;j<P;j++)
                best[0][i][j]=best[1][i][j]=-1;
        best[0][0][0]=0;
        p=1;
        for(it=v.begin();it!=v.end();it++,p=1-p)
        {
            r=*it%P;
            for(j=0;j<P;j++)
            {
                for(i=0;i<K;i++)
                {
                    if(best[1-p][i][j]!=-1)
                    {
                        best[p][i][j]=max(best[p][i][j],best[1-p][i][j]);
                        best[p][i+1][r]=max(best[p][i+1][r],best[1-p][i][j]+*it);
                    }
                }
                r++; // r=(j+*it)%P
                if(r==P)
                    r=0;
            }
            for(j=0;j<P;j++)
                best[p][K][j]=max(best[p][K][j],best[1-p][K][j]);
        }
        fout<<best[1-p][K][0]<<"\n";
        v.clear();
    }
    fout.close();
    return 0;
}