#include<cstdio>
#include<algorithm>
#define NMAX 300000+5
#define KMAX 5+2
#define PMAX 20+2
using namespace std;
int N,M,V[NMAX];
int cnt[PMAX][PMAX],nmr[KMAX*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]]=i;
        }
    }
    for(p=2;p<=20;p++)
    {
        for(i=0;i<=5;i++)
            for(j=0;j<=p;j++) dp[p][i][j]=-1;
        dp[p][0][0]=0;
        for(i=1;i<=nmr[p];i++)
            for(k=1;k<=5;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;
}