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

using namespace std;

vector<int> nr[21][20];

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

bool cmpf( const int &a, const int &b )
{
	return ( a> b );
}

void back( int l )
{
	int i,j;
	int maxc = 0;
	int ax = 0;
	if ( l == k+1 ) 
	{
		good = 1;
		for ( i = 0; i < p; i++ )
			if ( cfg[i] )
		{
			if ( nr[p][i].size() >= cfg[i] )
			{
				for ( j = 0; j < cfg[i] ; j++ )
					maxc += nr[p][i][j];
			}
			else
				good == 0;
		}
		if ( maxc % p == 0 && good )
			if ( maxc > costmax ) costmax = maxc;
	}
	else
	{
		for ( i = cfg[l-1]; i < p; i++ )
		{
			cfg[i] += 1;
			back( l+1 );
			cfg[i] -= 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 ].size() < 5 )
				nr[j][ aux%j ].push_back( aux );
			else
			if ( nr[j][ aux%j ][ nr[j][aux%j].size() - 1] <= aux ) 
			{
				nr[j][ aux%j ].push_back( aux );
				sort( nr[j][ aux%j ].begin(), nr[j][ aux%j ].end(), cmpf );
				nr[j][ aux%j ].pop_back();
			}
		}
	}

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

	fclose(stdin);
	fclose(stdout);

	return 0;
}