#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

#define FOR(i,s,d) for(i=(s);i<(d);++i)
#define pmax 21
#define kmax 6

int n,m,k,p,A[32][32][8],sol;

void doit(int k,int x,int i,int p)
{
	if(i==p)
	{
		if(!k&&sol<x&&x%p==0)
			sol=x;
		return ;
	}
	doit(k,x,i+1,p);
	int j;
	FOR(j,0,k)
	{
		if(!A[p][i][j])
			return ;
		x+=A[p][i][j];
		doit(k-j-1,x,i+1,p);
	}
}

int main()
{
	freopen("tricouri.in","r",stdin);
	freopen("tricouri.out","w",stdout);
	int ii,i,j,jj;
	scanf("%d %d",&n,&m);
	FOR(ii,0,n)
	{
		scanf("%d",&j);
		FOR(i,2,pmax)
		{
			jj=j%i;
			A[i][jj][kmax-1]=j;
			sort(A[i][jj],A[i][jj]+kmax);
			reverse(A[i][jj],A[i][jj]+kmax);
		}			
	}
	FOR(ii,0,m)
	{
		scanf("%d %d",&k,&p);
		sol=-1;
		doit(k,0,0,p);
		printf("%d\n",sol);
	}
	return 0;
}