#include <cstdio>
#include <algorithm>

using namespace std;

FILE*f=fopen("tricouri.in","r");
FILE*h=fopen("tricouri.out","w");

int n,m;

int d[21][21][6],a[300001],used[21][21];

int main(){
	fscanf(f,"%d%d",&n,&m);
	for ( int i=0;i<n;++i )
		fscanf(f,"%d",&a[i]);
	sort(a,a+n);
	for ( int i=n-1;i>=0;--i ){
		int neimportant=-1;
		for ( int j=2;j<=20;++j ){
			++used[j][a[i]%j];
			if ( used[j][a[i]%j]<5 )
				neimportant=a[i];
		}
		a[i]=neimportant;
	}
	for ( int i=n-1;i>=0;--i ){
		if ( a[i]==-1 )
			continue;
		int x=a[i];
		for ( int j=2;j<=20;++j )
			for ( int k=4;k>=0;--k )
				for ( int l=0;l<j;++l )
					if ( ((k==0)||d[j][l][k])&&
						 d[j][(d[j][l][k]+x)%j][k+1]<d[j][l][k]+x ){
							d[j][(d[j][l][k]+x)%j][k+1]=d[j][l][k]+x;
			}
	}
	//for ( int i=2;i<=20;++i ){
	//	for ( int j=1;j<=5;++j ){
	//		fprintf(h,"%d ",d[i][0][j]);
	//	}
	//	fprintf(h,"\n");
	//}
	for ( int i=0;i<m;++i ){
		int x,y;
		fscanf(f,"%d%d",&x,&y);
		if ( !d[y][0][x] )
			fprintf(h,"-1\n");
		else
			fprintf(h,"%d\n",d[y][0][x]);
	}
    return 0;
}