#include<stdio.h>
#include<algorithm>
using namespace std;
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,minn,jj;
int viz[22][22][7],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(p=2;p<=20;++p)
	{
		for(int i=1;i<=n;++i)
			if(viz[p][v[i]%p][0]<5)
			{
				
				viz[p][v[i]%p][0]++;
				viz[p][v[i]%p][viz[p][v[i]%p][0]]=v[i];
			}
			else
			{
				minn=viz[p][v[i]%p][1];
				jj=1;
				for(int j=2;j<=5;++j)
					if(minn>viz[p][v[i]%p][j])
					{
						jj=j;
						minn=viz[p][v[i]%p][j];
					}
					
				if(jj&&v[i]>viz[p][v[i]%p][jj])
					viz[p][v[i]%p][jj]=v[i];
			}
	}
	
	for(p=2;p<=20;++p)
		for(int i=0;i<p;++i)
			sort(viz[p][i]+1,viz[p][i]+viz[p][i][0]+1);
	
	for(int o=1;o<=m;++o)
	{
		fscanf(f,"%d%d",&k,&p);
		nr=0;
		
		for(int i=0;i<p;++i)
		{
			
			int x=viz[p][i][0];
			for(int j=x;j>=x-k+1&&j;--j)
				w[++nr]=viz[p][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;
}