#include<stdio.h>
FILE*f=fopen("tricouri.in","r");
FILE*g=fopen("tricouri.out","w");
int n,m,k,p,v[300001],w[401],a[6][22],y,nr,ok,nn,min,jj;
int viz[22][6],wiz[6][22][6];
int main()
{
	fscanf(f,"%d%d",&n,&m);
	for(int i=1;i<=n;++i)
		fscanf(f,"%d",&v[i]);
	nn=n;
	if(n>5)
		nn=5;
	for(int o=1;o<=m;++o)
	{
		fscanf(f,"%d%d",&k,&p);
		nr=0;
		for(int i=0;i<p;++i)
			viz[i][0]=0;
		for(int i=1;i<=n;++i)
			if(viz[v[i]%p][0]<k)
			{
				
				viz[v[i]%p][0]++;
				viz[v[i]%p][viz[v[i]%p][0]]=v[i];
			}
			else
			{
				min=viz[v[i]%p][1];
				jj=1;
				for(int j=2;j<=k;++j)
					if(min>viz[v[i]%p][j])
					{
						jj=j;
						min=viz[v[i]%p][j];
					}
					
				if(jj&&v[i]>viz[v[i]%p][jj])
					viz[v[i]%p][jj]=v[i];
			}
		for(int i=0;i<p;++i)
			for(int j=1;j<=viz[i][0];++j)
				w[++nr]=viz[i][j];
		for(int j=1;j<=k;++j)	
			for(int i=0;i<p;++i)
				a[j][i]=0;
		for(int i=1;i<=nr;++i)
			if(a[1][w[i]%p]<w[i])
			{
				a[1][w[i]%p]=w[i];
				wiz[1][w[i]%p][1]=i;
			}
		
		for(int i=2;i<=k;++i)
			for(int j=1;j<=nr;++j)
				for(int t=0;t<p;++t)
				{
					y=(t-w[j]%p+p)%p;
					if(a[i][t]<a[i-1][y]+w[j]&&a[i-1][y])
					{
						ok=0;
						for(int ii=1;ii<i;++ii)
							if(wiz[i-1][y][ii]==j)
								ok=1;
						if(!ok)
						{
							a[i][t]=a[i-1][y]+w[j];
							for(int ii=1;ii<i;++ii)
								wiz[i][t][ii]=wiz[i-1][y][ii];
							wiz[i][t][i]=j;
						}
					}
				}
		if(a[k][0])
			fprintf(g,"%d\n",a[k][0]);
		else
			fprintf(g,"-1\n");
	}
	
	
	fclose(f);
	fclose(g);
	return 0;
}