#include <cstdio>
#include <string>

#define fin  "tricouri.in"
#define fout "tricouri.out"

#define DBxG
#define FL

const int Nmax = 300010;

int N,M;
int v[Nmax];

int restb[20][7],a[106];
int dp1[6][20],dp2[6][20];

int ret[21][6];

inline void swapf(int &a,int &b)
{
	int aux;
	aux = a; a = b; b = aux;
}

inline int maxf(int a,int b)
{
	return (a>b)?(a):(b);
}

void prep()
{
	int i,j,k,P,val,vf;

	for ( P = 2; P <= 20; ++P )
	{
		memset(restb,0,sizeof(restb));

		for ( i = 1; i <= N; ++i )
		{
			val = v[i] % P;
			restb[val][++restb[val][0]]=v[i];
			vf = restb[val][0];
			while ( restb[val][vf] > restb[val][vf-1] && vf > 1 )
				swapf(restb[val][vf],restb[val][vf-1]),--vf;
			if ( restb[val][0] > 5 )
				--restb[val][0];
		}

		a[0] = 0;

		for ( i = 0; i < P; ++i )
		for ( j = 1; j <= restb[i][0]; ++j )
			a[ ++a[0] ] = restb[i][j];
#ifdef DBG
		printf("%d:\n",P);
		for ( i = 1; i <= a[0]; ++i )
			printf("%d ",a[i]);
		printf("\n\n");
#endif
		memset(dp1,0,sizeof(dp1));
		
		dp1[1][a[1]%P]=a[1];

		for ( i = 2; i <= a[0]; ++i )
		{
			memcpy(dp2,dp1,sizeof(dp1));

			for ( j = 1; j < 5; ++j )
			for ( k = 0; k < P; ++k )
				if ( dp1[j][k] )
					dp2[j+1][(k+a[i])%P] = maxf(dp2[j+1][(k+a[i])%P],dp1[j][k]+a[i]);
			if ( a[i] > dp2[1][a[i]%P] )
				dp2[1][a[i]%P] = a[i];

			memcpy(dp1,dp2,sizeof(dp2));
		}

		for ( j = 1; j <= 5; ++j )
			if ( dp1[j][0] > 0 )
				ret[ P ][ j ] = dp1[j][0];
			else
				ret[ P ][ j ] = -1;
	}
#ifdef DBG
	for ( i = 2; i <= 20; ++i,printf("\n") )
	for ( j = 1; j <= 5 ; ++j )
		printf("%d ",ret[i][j]);
#endif
}

void readsolve()
{
	int i,k,p;

	freopen(fin,"r",stdin);
#ifdef FL
	freopen(fout,"w",stdout);
#endif

	scanf("%d%d",&N,&M);

	for ( i = 1; i <= N; ++i )
		scanf("%d",&v[i]);

	prep();

	for ( i = 1; i <= M; ++i )
	{
		scanf("%d%d",&k,&p);
		printf("%d\n",ret[p][k]);
	}
}

int main()
{
	readsolve();
	return 0;
}