#include <fstream.h>
#define MaxN 300009
#define MaxK 9
#define MaxP 29

ifstream fin("tricouri.in");
ofstream fout("tricouri.out");

long x[MaxN],max,n;
int a[MaxP][MaxN],sol[MaxP],m,k,p,i,li,ls,kp,rest[MaxP],val;

void poz(int li,int ls,int lin)
{
	int i=0,j=-1,c;
	while(li<ls)
	{
		if(x[a[lin][li]]<x[a[lin][ls]])
		{
			c=a[lin][li];
			a[lin][li]=a[lin][ls];
			a[lin][ls]=c;
			c=i;
			i=-j;
			j=-c;
		}
		li+=i;
		ls+=j;
	}
	kp=li;
}
			
	

void quick(int li,int ls,int lin)
{
	if(li<ls)
	{
		poz(li,ls,lin);
		quick(li,kp-1,lin);
		quick(kp+1,ls,lin);
	}
}

void verif(int nr)
{
	int i,sum=0,sw=1,c,l;
	if(nr>k)
		sw=0;
	for(i=1;i<=nr && sw;i++)
		if(rest[sol[i]]<a[sol[i]][0])
		{
			rest[sol[i]]++;
			l=sol[i];
			c=rest[sol[i]];
			sum+=x[a[l][c]];
		}
		else
			sw=0;
	if(sw)
	{
		for(i=1;i<=(k-nr);i++)
			sum+=x[a[0][i]];
		if(sum>max)
			max=sum;
	}
}
	

void back(int k)
{
	int i;
	if(val==p)
		verif(k-1);
	else
		for(i=sol[k-1]+1;i<=p-val;i++)
		{
			sol[k]=i;
			val+=i;
			back(k+1);
			val-=i;
		}
}

void rez()
{
	int i,c;
	for(i=1;i<=n;i++)
	{
		c=x[i]%p;
		a[c][0]++;
		a[c][a[c][0]]=i;
	}
	for(i=0;i<p;i++)
		if(a[i][0]>1)
		{
			kp=0;
			quick(1,a[i][0],i);
		}
		
	back(1);
}

void afis()
{
	int i,j,c;
	if(max==0)
		fout<<-1<<'\n';
	else
		fout<<max<<'\n';
}

void gol()
{
	int i,j;
	for(i=0;i<p;i++)
	{
		for(j=1;j<=a[i][0];j++)
			a[i][j]=0;
		a[i][0]=0;
		rest[i]=0;
	}
}

int main()
{
	fin>>n>>m;
	for(i=1;i<=n;i++)
		fin>>x[i];
	for(i=1;i<=m;i++)
	{
		fin>>k>>p;
		max=0;
		rez();
		afis();
		gol();
	}
	fin.close();
	fout.close();
	return 0;
}