#include<stdio.h>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
struct
vector<int> y,R;
pair<int,int> q;
vector<pair<int,int> > Q[21];
int n,m,p,k,i,r,K,nq,sol[4000][7],i1,i2,i3,i4,i5,c,getsol(),pus[21],nec[21];
void read(),solve(),getsol1(),getsol2(),getsol3(),getsol4(),getsol5(),getdisp();
long long sf[101],sc,P[20][7];
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("tricouri.in","r",stdin);
	freopen("tricouri.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++){scanf("%d",&k);y.push_back(k);}
	sort(y.begin(),y.end());
	for(i=1;i<=m;i++)
	{
		sf[i]=-2;
		scanf("%d%d",&k,&p);
		q.first=k;q.second=i;
		Q[p].push_back(q);
	}
}
void solve()
{
	int k_old,k_new,i_old,i_new,j,poz[21],*s;
	for(p=2;p<=20;p++)
	{
		if(getsol())
		{
			getdisp();
			k_old=-1;i_old=-1;
			for(;nq+1;nq--)
			{
				k_new=Q[p][nq].first;
				i_new=Q[p][nq].second;
				if(k_new==k_old){sf[i_new]=sf[i_old];continue;}
				for(i=1;i<=c;i++)
				{
					s=sol[i];sc=0;
					if(s[k_new+1])break;
					for(j=1;j<=k_new;j++)poz[s[j]]=0;
					for(j=1;j<=k_new;j++)sc+=P[s[j]][++poz[s[j]]];
					for(j=1;j<=k_new;j++)if(poz[s[j]]>pus[s[j]])sc=-1;
					sf[i_new]=sf[i_new]>sc?sf[i_new]:sc;
				}
				k_old=k_new;i_old=i_new;
			}
		}
	}
	for(i=1;i<=m;i++)
		printf("%lld\n",sf[i]);
}
int getsol()
{
	nq=Q[p].size();
	if(!nq)return 0;
	sort(Q[p].begin(),Q[p].end());
	nq--;
	K=Q[p][nq].first;
	R.resize(0);
	for(i=0;i<K;i++)
		for(r=0;r<p;r++)
			R.push_back(r);
		if(K==1)getsol1();
		if(K==2)getsol2();
		if(K==3)getsol3();
		if(K==4)getsol4();
		if(K==5)getsol5();
	return c;
}
void getsol1()
{
	n=1;sol[1][1]=0;
}
void getsol2()
{
	c=0;
	for(i1=0;i1<p;i1++)
		for(i2=i1;i2<p;i2++)
			if(!R[i1+i2])
			{
				sol[++c][2]=i1;
				sol[c][1]=i2;
			}
}
void getsol3()
{
	c=0;
	for(i1=0;i1<p;i1++)
		for(i2=i1;i2<p;i2++)
			for(i3=i2;i3<p;i3++)
			if(!R[i1+i2+i3])
			{
				sol[++c][3]=i1;
				sol[c][2]=i2;
				sol[c][1]=i3;
			}
}
void getsol4()
{
	c=0;
	for(i1=0;i1<p;i1++)
		for(i2=i1;i2<p;i2++)
			for(i3=i2;i3<p;i3++)
				for(i4=i3;i4<p;i4++)
					if(!R[i1+i2+i3+i4])
					{
						sol[++c][4]=i1;
						sol[c][3]=i2;
						sol[c][2]=i3;
						sol[c][1]=i4;
					}
}
void getsol5()
{
	c=0;
	for(i1=0;i1<p;i1++)
		for(i2=i1;i2<p;i2++)
			for(i3=i2;i3<p;i3++)
				for(i4=i3;i4<p;i4++)
					for(i5=i4;i5<p;i5++)
						if(!R[i1+i2+i3+i4])
						{
							sol[++c][5]=i1;
							sol[c][4]=i2;
							sol[c][3]=i3;
							sol[c][2]=i4;
							sol[c][1]=i5;
						}
}
void getdisp()
{
	int Nec;//alegem cate maxim k pentru fiecare rest
	for(r=0;r<p;r++)
	{
		nec[r]=K;pus[r]=0;Nec+=K;
		for(i=1;i<=5;i++)P[r][i]=0;
	}
	for(i=n-1;(i+1)&&Nec;i--)
	{
		r=y[i]%p;
		if(nec[r])
		{
			Nec--;nec[r]--;P[r][++pus[r]]=(long long)y[i];
		}
	}
}


/*void p1()
{
	Cnt=0;
	for(p=2;p<=20;p++)
	{
		for(i=0;i<5;i++)
			for(r=0;r<p;r++)R[p].push_back(r);
		for(I[0]=0;I[0]<p;I[0]++)
		{
			S=I[0];
			for(I[1]=I[0];I[1]<p;I[1]++)
			{
				S+=I[1];
				for(I[2]=I[1];I[2]<p;I[2]++)
				{
					S+=I[2];
					for(I[3]=I[2];I[3]<p;I[3]++)
					{
						S+=I[3];
						for(I[4]=I[3];I[4]<p;I[4]++)
							if(!R[p][S+I[4]])
							{
								Cnt++;
								for(k=0;k<5;k++)
									Sol[Cnt][k]=I[k];
							}
						S-=I[3];
					}
					S-=I[2];
				}
				S-=I[1];
			}
		}
		U[p][5]=Cnt;
	}
	
}

*/