#include<stdio.h>
#define MAXIM 1000000
int n,nr,cnt,i,j,i1,j1,aux,x,P,K,min,pozmin,max,sum,sumrest;
int m[32][32][8],num[32][32],a[8];
void calcsuma(int sum,int sumrest)
{
	int i;
	sumrest%=P;
	a[K]=(P-sumrest)%P;
	if(num[P][a[K]]<m[P][a[K]][0])
	{
		sum+=m[P][a[K]][num[P][a[K]]+1];
		if(sum>max)
			max=sum;
  }
}
void back(int k)
{
	int i;
	if(k>=K)
		calcsuma(sum,sumrest);
	else
	{
		for(i=0;i<P;i++)
		if(num[P][i]<m[P][i][0])
		{
			num[P][i]++;
			a[k]=i;
			sum+=m[P][i][num[P][i]];
			sumrest+=i;
			back(k+1);
			sum-=m[P][i][num[P][i]];
			num[P][i]--;
			sumrest-=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;
					}
				if(x>min)
					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;
}