#include <cstdio>
#include <vector>
#include <algorithm>
#define fin  "tricouri.in"
#define fout "tricouri.out"
#define Nmax 1000

using namespace std;

int N,M,K,P,frcv[Nmax];
int bst1[20][6],bst2[20][6];
vector <int> aux,v;

int main() 
{
int i,j,k,tmp;	
	freopen(fin,"r",stdin); freopen(fout,"w",stdout);

	scanf("%d%d",&N,&M);

	for (i=0;i<N;++i) 
	{
		scanf("%d",&tmp);
		aux.push_back(tmp);
	}

	sort(aux.begin(),aux.end());

	for (i=(int)aux.size()-1;i>=0;--i)
		if (frcv[aux[i]%20]<=5) 
		{
			v.push_back(aux[i]);
			frcv[aux[i]%20]++;
		}	

	while ( M-- ) 
	{
		scanf("%d%d",&K,&P);
		for (i=0;i<(int)v.size();++i) 
		{
			for (j=0;j<P;++j)	
			for (k=1;k<=K;++k)
				if (bst1[j][k]) 
					bst2[(j+v[i])%P][k+1]=bst1[j][k]+v[i];
			
			bst2[v[i]%P][1]=max(bst2[v[i]%P][1],v[i]);

			for (j=0;j<P;++j)	
			for (k=1;k<=K;++k) {
				bst1[j][k]=max(bst1[j][k],bst2[j][k]);
				bst2[j][k]=0;
			}
			
		}

		if (!bst1[0][K]) bst1[0][K]=-1;

		printf("%d\n",bst1[0][K]);

		for (j=0;j<P;++j) 
		for (k=1;k<=K;++k) 
			bst1[j][k]=0;
	}

	return 0;
}