#include <cstdio>

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

int n,m;

int d[21][21][6];

int main(){
	fscanf(f,"%d%d",&n,&m);
	for ( int i=0;i<n;++i ){
		int x;
		fscanf(f,"%d",&x);
		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;
}