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

int v[300002];

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