#include <fstream>

#define z(i,s,d) for(i=(s);i<(d);++i)
std::fstream f("tricouri.in"),g("tricouri.out",std::_S_out);

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

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

int main()
{
	int q,l,i,j,w;
	f>>n>>m;
	z(q,0,n)
	{
		f>>j;
		z(i,2,21)
		{
			w=j%i;
			for(l=5;l&&j>A[i][w][l-1];l--)
				A[i][w][l]=A[i][w][l-1];
			A[i][w][l]=j;
		}
	}
	z(l,0,m)
	{
		f>>k>>p;
		s=-1;
		h(k,0,0,p);
		g<<s<<'\n';
	}
	return 0;
}