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

using namespace std;

int N,M,K,P;
int bst1[32][32],bst2[32][32];
vector <int> aux[20][20],v[21];

inline void swapf(int &a,int &b) { int aux; aux=a; a=b; b=aux; }

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);
		for (j=2;j<21;++j) {
			r=tmp%j;
			aux[j][r].push_back(tmp);
			k=(int)aux[j][r].size()-1;
			while (k!=0 && aux[j][r][k]>aux[j][r][k-1]) {
				swapf(aux[j][r][k],aux[j][r][k-1]);
				--k;
			}
			if (aux[j][r].size()>5)
				aux[j][r].erase(aux[j][r].end()-1,aux[j][r].end());
		}
	}

	for (j=0;j<21;++j) v[j].clear();

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

	while ( M-- ) 
	{
		scanf("%d%d",&K,&P);
		
		for (j=0;j<32;++j) 
		for (k=0;k<32;++k) 
			bst1[j][k]=bst2[j][k]=0;

		for (i=0;i<(int)v[P].size();++i) 
		{
			for (j=0;j<P;++j)	
			for (k=1;k<K;++k)
				if (bst1[j][k]) 
					bst2[(j+v[P][i])%P][k+1]=bst1[j][k]+v[P][i];
			
			bst2[v[P][i]%P][1]=v[P][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]);

	}

	return 0;
}