#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[20];
int bst1[20][6],bst2[20][6];
vector <int> aux[20],v;

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

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

	for (i=0;i<N;++i) 
	{
		scanf("%d",&tmp);
		r=tmp%20;
		aux[r].push_back(tmp);
		j=(int)aux[r].size()-1;
		while (j!=0 && aux[r][j]>aux[r][j-1]) {
			swap(aux[r][j],aux[r][j-1]);
			--j;
		}
		if ((int)aux[r].size()>5)
			aux[r].resize(5);
	}

	for (i=0;i<20;++i)
	for (j=0;j<(int)aux[i].size();++j)
		v.push_back(aux[i][j]);

	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;
}