#include<stdio.h>

#define dim 101

long n,m,k,p,a[dim],i,j,ii,jj,ij,s,max=0,iii,jjj;

int main()
{
	freopen("tricouri.in","r",stdin);
	freopen("tricouri.out","w",stdout);

	scanf("%ld%ld", &n, &m);

	for(i=1;i<=n;++i)

	scanf("%ld", &a[i]);

	for(j=1; j<=m; ++j)
	{
		scanf("%ld%ld", &k, &p);

		max=0;

		for(i=1;i<=k; ++i)
		{
		    if(k==3)
		    {

			for(ii=1;ii<n-1; ++ii)
			{

				for(jj=ii+1;jj<n; ++jj)

					for(ij=jj+1; ij<=n; ++ij)
					{
						s=a[ii]+a[jj]+a[ij];

						if(s>max && s%p==0)

							max=s;

					 }
			  }
		    }
		    if(k==1)
		    {
			max=0;

                        s=0;

			for(ii=1;ii<=n;ii++)
			{
				if(a[ii]%p==0)

					s=a[ii];

				if(s>max)

					max=s;
			}
		    }
		    if(k==2)
		    {
			for(ii=1;ii<n; ++ii)
			{

				for(jj=ii+1;jj<=n; ++jj)
				{
					s=a[ii]+a[jj];

					if(s>max && s%p==0)

						max=s;

				}
			}
		    }
		    if(k==4)
		    {
			for(ii=1;ii<n-2; ++ii)
			{

				for(jj=ii+1;jj<n-1; ++jj)

					for(iii=jj+1; iii<n; ++iii)

					for(ij=iii+1; ij<=n; ++ij)
					{
						s=a[ii]+a[jj]+a[ij]+a[iii];

						if(s>max && s%p==0)

							max=s;

					 }
			  }
		    }
		    if(k==5)
		    {
			for(ii=1;ii<n-3; ++ii)
			{

				for(jj=ii+1;jj<n-2; ++jj)

					for(iii=jj+1; iii<n-1; ++iii)

						for(jjj=iii+1;jjj<n; ++jjj)


							for(ij=jjj+1; ij<=n; ++ij)
							{
							s=a[ii]+a[jj]+a[ij]+a[iii]+a[jjj];

							if(s>max && s%p==0)

								max=s;

							 }
			  }
		    }


		}
	 if(max==0)

		  printf("-1\n");

	 else
		  printf("%ld\n", max);
	 }

	 return 0;
}