#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define nmax 300001
#define oo 1000000000
#define max(a,b) (a>b?a:b)

int i,j,l,n,nn,m,a[128],b[nmax],bb[22],best[6][21],bn,k,p,kk[128],pp[128],ss[128],pv[21];

int fc(const void *a,const void *b)
{
	return *(int*)b-*(int*)a;
}

int main()
{
	freopen("tricouri.in","r",stdin);
	freopen("tricouri.out","w",stdout);

	scanf("%d%d",&nn,&m);
	for (i=0;i<nn;i++)
		scanf("%d",b+i);
	qsort((void*)b,nn,sizeof(b[0]),fc);
	for (i=0;i<m;i++)
		scanf("%d%d",kk+i,pp+i),pv[pp[i]]=max(pv[pp[i]],kk[i]);
	for (p=2;p<=20;p++)
		if (pv[p])
	{
		memset(bb,0,sizeof(bb));
		n=0;
		for (i=0;i<nn;i++)
			if (bb[b[i]%p]<5)
				bb[b[i]%p]++,a[n]=b[i],++n;

		k=pv[p];
		for (i=0;i<6;i++)
			for (j=0;j<p;j++)
				best[i][j]=-oo;
		best[0][0]=0;
		for (i=0;i<n;i++)
		{
			for (j=k-1;j>=0;j--)
				for (l=0;l<p;l++)
					if (best[j+1][(l+a[i])%p]<best[j][l]+a[i])
						best[j+1][(l+a[i])%p]=best[j][l]+a[i];
		}
		for (i=0;i<m;i++)
			if (pp[i]==p)
				ss[i]=(best[kk[i]][0]>=0?best[kk[i]][0]:-1);
	}
	for (i=0;i<m;i++)
		printf("%d\n",ss[i]);

	return 0;
}