#include<fstream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstdlib>
#define LG 1500000
using namespace std;
int n,m,K,P;
vector <int> G[21][21],v;
int best[2][6][21],ind;
char buffer[LG];

inline void Citeste(int &x)
{
	while(buffer[ind]<'0' || '9'<buffer[ind])
	{
		ind++;
		if(ind==LG)
		{
			fread(buffer,1,LG,stdin);
			ind=0;
		}
	}
	x=0;
	while('0'<=buffer[ind] && buffer[ind]<='9')
	{
		x=x*10+buffer[ind]-'0';
		ind++;
		if(ind==LG)
		{
			fread(buffer,1,LG,stdin);
			ind=0;
		}
	}
}

int main()
{
	int i,j,x,r,p;
	vector <int>::iterator it;
	
	freopen("tricouri.in","r",stdin);
	fread(buffer,1,LG,stdin);
	
	Citeste(n); Citeste(m);
	for(i=1;i<=n;i++)
	{
		Citeste(x);
		for(j=2;j<=20;j++)
		{
			r=x%j;
			G[j][r].push_back(x);
			sort(G[j][r].begin(),G[j][r].end(),greater<int>());
			if(G[j][r].size()==6)
				G[j][r].pop_back();
		}
	}
	ofstream fout("tricouri.out");
	while(m--)
	{
		Citeste(K); Citeste(P);
		for(i=0;i<P;i++)
			for(it=G[P][i].begin();it!=G[P][i].end();it++)
				v.push_back(*it);
		for(i=0;i<=K;i++)
			for(j=0;j<P;j++)
				best[0][i][j]=best[1][i][j]=-1;
		best[0][0][0]=0;
		p=1;
		for(it=v.begin();it!=v.end();it++,p=1-p)
		{
			r=*it%P;
			for(j=0;j<P;j++)
			{
				for(i=0;i<K;i++)
				{
					if(best[1-p][i][j]!=-1)
					{
						best[p][i][j]=max(best[p][i][j],best[1-p][i][j]);
						best[p][i+1][r]=max(best[p][i+1][r],best[1-p][i][j]+*it);
					}
				}
				r++; // r=(j+*it)%P
				if(r==P)
					r=0;
			}
			for(j=0;j<P;j++)
				best[p][K][j]=max(best[p][K][j],best[1-p][K][j]);
		}
		fout<<best[1-p][K][0]<<"\n";
		v.clear();	
	}
	fout.close();
	return 0;
}