#include<stdio.h>
#define MAXIM 2000000
int n,nr,cnt,i,j,i1,j1,aux,x,P,K,min,pozmin,cost,max;
int m[21][21][7],num[21][21],a[6],fol[21];
void calcsuma()
{
	int i,s=0,j,ok=0;
	for(i=0;i<=20;i++)
		fol[i]=0;
	for(i=1;i<K;i++)
	{
		s+=a[i];
		fol[a[i]]++;
	}
	s%=P;
	a[K]=P-s;
	fol[a[K]]++;
	if(fol[a[K]]<=m[P][a[K]][0])
	{
		s=0;
		ok=1;
		for(i=0;i<P;i++)
		for(j=1;j<=fol[i];j++)
			s+=m[P][i][j];
	}
	if(s>max&&ok)
	max=s;
}
void back(int k)
{
	int i;
	if(k>=K)
		calcsuma();
	else
	{
		for(i=0;i<P;i++)
		if(num[P][i]<m[P][i][0])
		{
			num[P][i]++;
			a[k]=i;
			back(k+1);
			num[P][i]--;
		}
	}
}


int main(void)
{
	freopen("tricouri.in","r",stdin);
	freopen("tricouri.out","w",stdout);
	scanf("%d%d",&n,&nr);
	for(cnt=1;cnt<=n;cnt++)
	{
		scanf("%d",&x);
		for(i=2;i<=20;i++)
		{
			j=x%i;
			if(m[i][j][0]<5)
			{
				m[i][j][0]++;
				m[i][j][m[i][j][0]]=x;
			}
			else
			{
				min=MAXIM;
				for(i1=1;i1<=5;i1++)
					if(m[i][j][i1]<min)
					{
						min=m[i][j][i1];
						pozmin=i1;
					}
				m[i][j][pozmin]=x;
			}
		}
	}
	for(i=2;i<=20;i++)
		for(j=0;j<i;j++)
				{
					for(i1=1;i1<m[i][j][0];i1++)
						for(j1=i1+1;j1<=m[i][j][0];j1++)
							if(m[i][j][i1]<m[i][j][j1])
							{
								aux=m[i][j][i1];
								m[i][j][i1]=m[i][j][j1];
								m[i][j][j1]=aux;
							}
				}
	for(i=1;i<=nr;i++)
	{
		scanf("%d%d",&K,&P);
		max=-1;
		back(1);
		printf("%d\n",max);
	}
	return 0;
}