#include<stdio.h>
#include<stdlib.h>
#define NMAX 300000

struct cer{int k,p,r,id;};
typedef cer*pcer;
cer w[100];

int v[NMAX]={0},n;

int fcmp0(void const*a,void const*b){
return *((int*)b)-*((int*)a);
}

int ma[21][20][6];

int fcmp(void const*a,void const*b){
return ((pcer)a)->p-((pcer)b)->p;
}
int fcmp2(void const*a,void const*b){
return ((pcer)a)->id-((pcer)b)->id;
}

int main(){
freopen("tricouri.in","r",stdin);
freopen("tricouri.out","w",stdout);
int m,i,j,k,s,ok,a,b,c,d,e,sm,nec,s1,s2,s3,r,nr,mai;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++) scanf("%d",&v[i]);
for(i=0;i<m;i++) {scanf("%d%d",&w[i].k,&w[i].p);w[i].id=i;}
qsort(w,m,sizeof(w[0]),fcmp);
for(i=0;i<n;++i){
	mai=19;
	for(d=2;d<21&&mai;++d){
		r=v[i]%d;
		nr=ma[d][r][0];
		if(nr<5) {
			nr++;
			ma[d][r][nr]=v[i];
			ma[d][r][0]=nr;
			if(nr==5) mai--;
			break;
			}
		}
	}
d=0;
for(i=2;i<21;++i)
	for(j=0;j<20;++j)
		for(k=1;k<=ma[i][j][0];++k){
			v[d]=ma[i][j][k],d++;
			}
n=d;
qsort(v,n,sizeof(v[0]),fcmp0);

for(i=0;i<m;i++){
	s=0;ok=0;sm=-1;
	if(i&&w[i].k==w[i-1].k&&w[i].p==w[i-1].p) {
		w[i].r=w[i-1].r;continue;
		}
	switch (w[i].k){
	case 1:a=0;
		   while(v[a]%w[i].p!=0) a++;
		   if(a<n&&v[a]%w[i].p==0) sm=v[a];
		   break;
	case 2:if(v[0]+v[1]<w[i].p) ;
		   else
		   for(a=0;a<n-1;a++){
			  if(a<n-2&&v[a]==v[a+2]) continue;
			  if(v[a]+v[a+1]<=sm||v[a]+v[a+1]<w[i].p) break;
			  nec=w[i].p-v[a]%w[i].p;
			  if(nec==w[i].p) nec=0;
			  for(b=a+1;b<n;b++){
				if(b<n-1&&v[b]==v[b+1]) continue;
				if(v[b]%w[i].p!=nec) continue;
				s=v[a]+v[b];
				if(s>sm) sm=s;
				else break;
				}
		   }
		   break;
	case 3:if(v[0]+v[1]+v[2]<w[i].p) break;
		   for(a=0;a<n-2;a++){
			  if(a<n-3&&v[a]==v[a+3]) continue;
			  if(v[a]+v[a+1]+v[a+2]<=sm||v[a]+v[a+1]+v[a+2]<w[i].p) break;
			  for(b=a+1;b<n-1;b++){
				if(b<n-2&&v[b]==v[b+2]) continue;
				s1=v[a]+v[b];
				if(s1+v[b+1]<=sm||s1+v[b+1]<w[i].p) break;
			  nec=w[i].p-s1%w[i].p;
			  if(nec==w[i].p) nec=0;
				for(c=b+1;c<n;c++){
					if(c<n-1&&v[c]==v[c+1]) continue;
					if(v[c]%w[i].p!=nec) continue;
					s=s1+v[c];
				if(s>sm) sm=s;
				else break;
					}
				}
		   }
		   break;
	case 4:if(v[0]+v[1]+v[2]+v[3]<w[i].p) break;
		   for(a=0;a<n-3;a++){
			  if(a<n-4&&v[a]==v[a+4]) continue;
			  if(v[a]+v[a+1]+v[a+2]+v[a+3]<=sm||
				 v[a]+v[a+1]+v[a+2]+v[a+3]<w[i].p) break;
			  for(b=a+1;b<n-2;b++){
				if(b<n-3&&v[b]==v[b+3]) continue;
				s1=v[a]+v[b];
				if(s1+v[b+1]+v[b+2]<=sm||s1+v[b+1]+v[b+2]<w[i].p) break;
				for(c=b+1;c<n-1;c++){
					if(c<n-2&&v[c]==v[c+2]) continue;
					s2=s1+v[c];
					if(s2+v[c+1]<=sm||s2+v[c+1]<w[i].p) break;
					nec=w[i].p-s2%w[i].p;
					if(nec==w[i].p) nec=0;
					for(d=c+1;d<n;d++){
						if(d<n-1&&v[d]==v[d+1]) continue;
						if(v[d]%w[i].p!=nec) continue;
						s=s2+v[d];
				if(s>sm) sm=s;
				else break;
					}
				}
			  }
		   }
		   break;
	case 5:if(v[0]+v[1]+v[2]+v[3]+v[4]<w[i].p) break;
		   for(a=0;a<n-4;a++){
			  if(a<n-5&&v[a]==v[a+5]) continue;
			  if(v[a]+v[a+1]+v[a+2]+v[a+3]+v[a+4]<=sm||
				 v[a]+v[a+1]+v[a+2]+v[a+3]+v[a+4]<w[i].p) break;
			  for(b=a+1;b<n-3;b++){
				if(b<n-4&&v[b]==v[b+4]) continue;
				s1=v[a]+v[b];
				if(s1+v[b+1]+v[b+2]+v[b+3]<=sm||
				   s1+v[b+1]+v[b+2]+v[b+3]<w[i].p) break;
				for(c=b+1;c<n-2;c++){
					if(c<n-3&&v[c]==v[c+3]) continue;
					s2=s1+v[c];
					if(s2+v[c+1]+v[c+2]<=sm||
					   s2+v[c+1]+v[c+2]<w[i].p) break;
					for(d=c+1;d<n-1;d++){
						if(d<n-2&&v[d]==v[d+2]) continue;
						s3=s2+v[d];
						if(s3+v[d+1]<=sm||s3+v[d+1]<w[i].p) break;
						nec=w[i].p-s3%w[i].p;
						if(nec==w[i].p) nec=0;
						for(e=d+1;e<n;e++){
						if(e<n-1&&v[e]==v[e+1]) continue;
						if(v[e]%w[i].p!=nec) continue;
						s=s3+v[e];
						if(s>sm) sm=s;
						else break;
						}
					}
				}
			  }
		   }
		   break;
	}
	w[i].r=sm;
	}
qsort(w,m,sizeof(w[0]),fcmp2);
for(i=0;i<m;++i) printf("%d\n",w[i].r);
return 0;
}