#include <fstream>
#define d(i,s,d) for(i=(s);i<(d);++i)
int n,m,k,p,A[32][32][8],sol,z,w,i,j,l;
std::fstream f("tricouri.in"),g("tricouri.out",std::_S_out);
void r(int k,int x,int i,int p)
{
    if(i==p)
    {
        if(!k&&sol<x&&x%p==0)
            sol=x;
        return;
	}
	r(k,x,i+1,p);
	int j;
	d(j,0,k){
    if(!A[p][i][j])
			return ;
		x+=A[p][i][j];
		r(k-j-1,x,i+1,p);
	}
}

int main()
{
	f>>n>>m;
	d(z,0,n)
	{
		scanf("%d",&j);
		d(i,2,21)
		{
			l=j%i;
			for(w=5;w&&j>A[i][l][w-1];w--)
				A[i][l][w]=A[i][l][w-1];
			A[i][l][w]=j;
		}
	}
	d(w,0,m)
	{
		scanf("%d%d",&k,&p);
		sol=-1;
		r(k,0,0,p);
		printf("%d\n",sol);
	}
	return 0;
}