#include <stdio.h>
#include <iostream>

using namespace std;

int nr[21][20];

int n,m;
int k,p;
int aux;
int costmax;
int cfg[6];

void back( int l )
{
	int i;
	int maxc = 0;
	int ax = 0;
	if ( l == k+1 ) 
	{
		for ( i = 1; i <= k; i++ )
		{
			maxc += nr[p][ cfg[i] ];
			ax += cfg[i];
		}
		if ( ax % p == 0 )
			if ( maxc > costmax ) costmax = maxc;
	}
	else
	{
		for ( i = cfg[l-1]+1; i <= p; i++ )
		{
			cfg[l] = i;
			back( l+1 );
		}
	}
	
}

int main()
{
	int i,j;
	freopen("tricouri.in","r",stdin);
	freopen("tricouri.out","w",stdout);

	scanf("%d %d\n", &n, &m);

	for ( i = 1; i <= n; i++ )
	{
		scanf("%d ", &aux );
		for ( j = 1; j <= 20; j++ )
			if ( nr[j][ aux%j ] < aux ) nr[j][ aux%j ] = aux;
	}
	while ( m )
	{
		m--;
		cfg[0] = -1;
		scanf("%d %d", &k, &p);
		costmax = 0;
		back(1);
		if ( costmax == 0 )
			printf("-1\n");
		else	printf("%d\n", costmax );
	}

	fclose(stdin);
	fclose(stdout);

	return 0;
}