#include<stdio.h>
#include<algorithm>
using namespace std;
long x[300001],n,m,i,j,sum,p,k,o,maxim;
int main()
{
	freopen ("tricouri.in","rt",stdin);
	freopen ("tricouri.out","wt",stdout);

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

	for (i=1;i<=n;i++)
		scanf("%ld",&x[i]);

	sort(x,x+n);

	for (o=1;o<=m;o++)
	{
		scanf("%ld %ld",&k,&p);
		maxim=-1;
		for (i=n;i>=k;i--)
		{
			sum=0;
			for (j=i;j>=i-k+1;j--)
				sum+=x[j];

			maxim=(sum%p==0)&&(sum>maxim)?sum:maxim;
		}

		printf("%ld\n",maxim);
	}
	return 0;
}