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

#define nmax 300010
#define oo 1000000000

int i,j,l,n,m,a[nmax],best[2][10][25],bn,k,p,kk[128],pp[128],ss[128],pv[21];

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

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

	return 0;
}