#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;

int i,j,n,m,a[300001],fol[32],k,p,sum,v[10],smax;

vector< int >  m1[32][32];

void verifica()
{
	int s=0;
	sum=0;
	for(int i=1;i<k;++i)
		if(m1[ p ][ v[i] ][ fol[ v[i] ] ]) 
		{	
			sum+=m1[ p ][ v[i] ][ fol[ v[i] ] ];
			s+=v[i];
			fol[v[i]]++;
		}
		else 
		{
			sum=-1;
			memset(fol,0,sizeof(fol));
			return ;
		}
	s=(p-s%p)%p;
	
	if(m1[p][s][fol[s]])
		sum+=m1[p][s][fol[s]];
	else 
	    sum=-1;
	memset(fol,0,sizeof(fol));
}

void back(int i)
{
	if(i==k)
	{	verifica();
		if( sum>smax) 
			smax=sum;
		return ;
	}
	
	for(int t=v[i-1];t<p;++t)
	{
		v[i]=t;
		back(i+1);
	}
}

int main()
{
	freopen("tricouri.in","r",stdin);
	freopen("tricouri.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	
	for(i=1;i<=n;++i)
		scanf("%d",&a[i]);
	
	sort(a+1,a+n+1);
	
	for(i=n;i>0;--i)
		for(j=1;j<=20;++j)
		{
			int x=a[i]%j;
			if(m1[j][x].size()<5) 
				m1[j][x].push_back(a[i]);
		}
	for(i=1;i<=20;++i)
		for(j=0;j<i;++j)
			if(m1[i][j].size()<5)
				for(int t=m1[i][j].size()+1;t<=5;++t) m1[i][j].push_back(0);
		
	for(i=1;i<=m;++i)
	{
		scanf("%d%d",&k,&p);
		
		smax=-1000000;
		
		back(1);
		
		printf("%d\n",smax);
	}
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}