#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
int n,m,K,P;
vector <int> G[21][21],v;
int best[2][6][21];

int main()
{
	int i,j,x,r,p;
	vector <int>::iterator it;
	ifstream fin("tricouri.in");
	ofstream fout("tricouri.out");
	fin>>n>>m;
	for(i=1;i<=n;i++)
	{
		fin>>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();
		}
	}
	while(m--)
	{
		fin>>K>>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();	
	}
	fin.close();
	fout.close();
	return 0;
}