#include<stdio.h>
int n,m,p,k,i,j,P,rn,rc,rv,r,R[50],rr[22];
long long v,pp,sol[110],u[22][7],x[110],best[110][22][6];
void solve();
int main()
{
	freopen("tricouri.out","w",stdout);
	solve();
	return 0;
}
void solve()
{
	for(p=2;p<=20;p++)
	{
		pp=(long long)p;
		for(r=0;r<p;r++)R[r]=R[r+p]=r;
		freopen("tricouri.in","r",stdin);
		scanf("%d%d",&n,&m);
		for(r=0;r<p;r++)
			for(i=1;i<=5;i++)u[r][i]=0;
		for(;n;n--)
		{
			scanf("%lld",&v);
			r=v%p;
			for(i=1;i<=5;i++)if(u[r][i]<v)break;
			for(j=6;j>i;j--)u[r][j]=u[r][j-1];
			u[r][i]=v;
		}
		for(r=0;r<p;r++)
			for(i=1;i<=5;i++)
				{ if(u[r][i])x[++n]=u[r][i];rr[n]=(int)(x[n]%pp);}
		for(k=1;k<=5;k++)
			for(r=0;r<p;r++)
				for(i=1;i<=n;i++)
					best[i][r][k]=0;
		for(i=1;i<=n;i++)
		{
			for(r=0;r<p;r++)best[i][r][1]=best[i-1][r][1];
			r=x[i]%p;
			best[i][r][1]=best[i-1][r][1]>x[i]?best[i-1][r][1]:x[i];
		}
		for(k=2;k<=5;k++)
		{
			for(i=k;i<=n;i++)
			{
				rc=rr[i];
				for(rv=0;rv<p;rv++)
					if(best[i-1][rv][k-1])
					{
						rn=R[rv+rc];
						best[i][rn][k]=best[i][rn][k]>x[i]+best[i-1][rv][k-1]?best[i][rn][k]:x[i]+best[i-1][rv][k-1];
					}
				for(r=0;r<p;r++)best[i][r][k]=best[i][r][k]>best[i-1][r][k]?best[i][r][k]:best[i-1][r][k];
			}
		}
		for(i=1;i<=m;i++)
		{
			scanf("%d%d",&k,&P);
			if(p-P)continue;
			sol[i]=best[n][0][k];
		}
	}
	for(i=1;i<=m;i++)
		sol[i]?printf("%lld\n",sol[i]):printf("-1\n");
}