#include<cstdio>
#include<algorithm>
#define NMAX 300005
#define KMAX 6
#define PMAX 21
using namespace std;
int N,M,V[NMAX];
int cnt[PMAX][PMAX],nmr[PMAX],A[PMAX][KMAX*PMAX];
int dp[PMAX][KMAX][PMAX];
bool crit(int A,int B)
{
    return A>B;
}
int main()
{
    int i,j,k,p,r,f;
    freopen("tricouri.in","r",stdin);
    freopen("tricouri.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(i=1;i<=N;i++) scanf("%d",&V[i]);
    sort(V+1,V+N+1,crit);
    for(i=1;i<=N;i++)
    {
        for(p=2;p<=20;p++)
        {
            if(cnt[p][V[i]%p]>=5) continue;
            cnt[p][V[i]%p]++;
            A[p][++nmr[p]]=V[i];
        }
    }
    for(p=2;p<=20;p++)
    {
        for(i=0;i<=5;i++)
            for(j=0;j<=20;j++) dp[p][i][j]=-1;
        dp[p][0][0]=0;
        for(i=1;i<=nmr[p];i++)
            for(k=5;k>=1;k--)
                for(r=0;r<=p-1;r++)
                {
                    f=r-(A[p][i]%p);
                    f=(f<0)?f+p:f;
                    if(dp[p][k-1][f]!=-1) dp[p][k][r]=max(dp[p][k][r],dp[p][k-1][f]+A[p][i]);
                }
    }
    for(;M;--M)
    {
        scanf("%d%d",&k,&p);
        printf("%d\n",dp[p][k][0]);
    }
    return 0;
}