#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() == 0 )
				nr[j][ aux%j ].push_back( aux );
			else
			if ( nr[j][ aux%j ][ nr[j][aux%j].size() - 1] <= aux || nr[j][ aux%j ].size() < 5) 
			{
				nr[j][ aux%j ].push_back( aux );
				sort( nr[j][ aux%j ].begin(), nr[j][ aux%j ].end(), cmpf );
				if ( nr[j][ aux%j ].size() > 5 )
					nr[j][ aux%j ].pop_back();
			}
		}
	}
/*
	for ( i = 1; i <= 20; i++ )
		for ( j = 0; j < i; j++ )
		if ( nr[i][j].size() )
		{	
			printf("%d %d\n", i,j);
			for ( k = 0; k < nr[i][j].size(); k++ )
				printf("%d ", nr[i][j][k] );
			printf("\n");
		}*/
	while ( m )
	{
		m--;
		for ( i =0; i<= 20; i++)
			cfg[i] = 0;
		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;
}