using namespace std;
#include<cstdio>
#include<cstring>
#include<algorithm>
#define Nm 300000
#define Km 6
#define Pm 21

int main()
{
    int A[Nm],M[2][Km][Pm][Pm],V[Km*Pm*Pm],Nr[Pm][Pm],n,m,i,j,k,c,p,l=0;

    freopen("tricouri.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(i=0;i<n;++i)
        scanf("%d",A+i);
        
    sort(A,A+n);
    for(j=2;j<Pm;++j)
        memset(Nr[j],0,Pm*sizeof(int));
    for(i=n-1;i>=0;--i)
        for(j=2;j<Pm;++j)
            if(Nr[j][A[i]%j]<Km-1)
            {
                V[l++]=A[i];
                ++Nr[j][A[i]%j];
                break;
            }

    for(i=0;i<Km;++i)
        for(j=2;j<Pm;++j)
            for(k=0;k<j;++k)
                M[0][i][j][k]=-1;
    for(j=2;j<Pm;++j)
        M[0][0][j][0]=0;

    c=1; p=0;
    for(--l;l>=0;--l)
    {
        for(i=0;i<Km;++i)
            for(j=2;j<Pm;++j)
                memcpy(M[c][i][j],M[p][i][j],sizeof(M[c][i][j]));
        for(i=0;i<Km-1;++i)
            for(j=2;j<Pm;++j)
                for(k=0;k<j;++k)
                    if(M[p][i][j][k]!=-1
                    && M[p][i][j][k]+V[l]>M[c][i+1][j][(k+V[l])%j])
                        M[c][i+1][j][(k+V[l])%j]=M[p][i][j][k]+V[l];
        c^=1; p^=1;
    }

    freopen("tricouri.out","w",stdout);
    while(m--)
    {
        scanf("%d%d",&k,&j);
        printf("%d\n",M[p][k][j][0]);
    }

    return 0;
}