#include <cstdio>
#include <algorithm>
using namespace std;

int v[300002];

int main()
{
	int q,n,m,i,j,k,p,nr[23][6],kk[105],x,w,sum[6][23];
	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);
	for (i=1;i<=m;++i)
	{
		scanf("%d %d",&k,&p);
		for (j=0;j<p;++j) nr[j][0]=0;
		q=0,w=0;
		for (j=n;j>0 && q<k ;--j)
			if (nr[v[j]%p][0]==k) ++q,nr[v[j]%p][0]*=-1; else
				++nr[v[j]%p][0],nr[v[j]%p][nr[v[j]%p][0]]=v[j],++w,kk[w]=v[j];
		
		for (j=0;j<=k;++j)
			for (q=0;q<p;++q)
				sum[j][q]=-1;
		sum[0][0]=0;
		
		for (j=1;j<=w;++j)
			{
				for (q=k;q>1;--q)  
				for (x=0;x<p;++x) //rest
					if ((sum[q-1][x]>0) && (sum[q][(x+kk[j]%p)%p]<sum[q-1][x]+kk[j]))
						sum[q][(x+kk[j]%p)%p]=sum[q-1][x]+kk[j];
				if (sum[1][kk[j]%p]<kk[j])
					sum[1][kk[j]%p]=kk[j];
	    	}
					
		printf("%d\n",sum[k][0]);
	}
return 0;}