#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fi("tricouri.in");
ofstream fo("tricouri.out");
int N,T,t,i,j,K,P,aux,k,v;
vector <int> S[20];
int B[300001];
int X[101], nx;
vector <int> :: iterator it;
int A[101][20][6];
int suma;

int f(int a, int P)
// returneaza valoarea care ii lipseste lui a 
// pentru a fi multiplu de P
{
	return P-a%P;
}

int main()
{
	fi>>N>>T;
	for (i=1;i<=N;i++)
		fi>>B[i];
	for (t=1;t<=T;t++)
	{
		fi>>K>>P;
		for (i=0;i<=P-1;i++)
			S[i].clear();
		for (i=1;i<=N;i++)
			S[B[i]%P].push_back(B[i]);
	
	for (i=0;i<=P-1;i++)
		sort(S[i].begin(),S[i].end());
	nx=0;
	for (i=0;i<=P-1;i++)
	{
		if (S[i].size()<=K)
			for (it=S[i].begin();it!=S[i].end();it++)
				X[++nx]=(*it);
		else
		{
			it=S[i].end();
			for (j=1;j<=K;j++)
			{
				it--;
				X[++nx]=(*it);
			}
		}
	}
	for (i=1;i<=nx-1;i++)
		for (j=i+1;j<=nx;j++)
			if (X[i]<X[j])
			{
				aux=X[i];
				X[i]=X[j];
				X[j]=aux;
			}
	for (i=1;i<=nx;i++)
		for (j=0;j<=P-1;j++)
			for (k=1;k<=K;k++)
				A[i][j][k]=0;
	// primul nivel din A (k=1)
	for (i=1;i<=nx;i++)
		if (A[i][B[i]%P][1]==0)
			A[i][B[i]%P][1]=X[i];
	for (i=2;i<=nx;i++)
		for (j=0;j<=P-1;j++)
			if (A[i][j][1]<A[i-1][j][1])
				A[i][j][1]=A[i-1][j][1];
	for (k=2;k<=K;k++)
	{
		// se determina nivelul k din matricea A
		for (i=1;i<=k-1;i++)
				for (j=0;j<=P-1;j++)
					A[i][j][k]=0;
		suma=0;
		for (i=1;i<=k;i++)
			suma=suma+X[i];
		A[k][suma%P][k]=suma;
		for (i=k+1;i<=nx;i++)
			for (j=0;j<=P-1;j++)
			{
				// se determina A[i][j][k]
				A[i][j][k]=A[i-1][j][k];
				v=f(P+X[i]-j,P);
				if (X[i]+A[i-1][v][k-1]>A[i][j][k])
					A[i][j][k]=X[i]+A[i-1][v][k-1];
			}
	}
	if (A[nx][0][K]==0)
		fo<<-1<<endl;
	else
		fo<<A[nx][0][K]<<endl;
	}
	fi.close();
	fo.close();
	return 0;
}