#include<fstream>
#include<algorithm>
#include<cstring>
using namespace std;
ifstream f("tricouri.in");
ofstream g("tricouri.out");
int n,m,i,j,p,k,nr,sol[22][6][21],b[110],a[300100],v[22];
inline void rez(int p)
{
    int i,m,x,k,j,c[6][21],a[6][21];
    memset(a,0,sizeof(a));
    memset(c,0,sizeof(c));
    for(i=1;i<=nr;++i)
    {
        m=b[i]%p;
        for(j=1;j<=5;++j)
        for(k=0;k<p;++k)
        {
            x=k-m;
            if(x<0)
            x+=p;
            if(j==1&&x>0)
            continue;
            if(!a[j-1][x]&&j>1)
            continue;
            c[j][k]=max(c[j][k],a[j-1][x]+b[i]);
        }
        memcpy(a,c,sizeof(c));
    }
    memcpy(sol[p],c,sizeof(c));
}
int main()
{
    f>>n>>m;
    for(i=1;i<=n;++i)
    f>>a[i];
    sort(a+1,a+n+1);
    for(p=2;p<=20;++p)
    {
        nr=0;
        memset(v,0,sizeof(v));
        for(i=n;i;--i)
        {
            if(v[a[i]%p]<5)
            {
                ++v[a[i]%p];
                b[++nr]=a[i];
            }
        }
        rez(p);
    }
    for(i=1;i<=m;++i)
    {
        f>>k>>p;
        if(!sol[p][k][0])
        g<<-1<<'\n';
        else
        g<<sol[p][k][0]<<'\n';
    }
    return 0;
}