#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;

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

bool cmpf2( const int &a, const int &b )
{
	return ( a < b );
}

inline void back( int l, int maxc, int mm )
{
	int i,j;
	int ax = 0;
	if ( l == k+1 ) 
	{
		if ( maxc % p == 0 )
			if ( maxc > costmax ) costmax = maxc;
	}
	else
	{
		for ( i = mm; i < p; i++ )
		{
			if ( nr[p][i].size() )
			{
				ax=nr[p][i][ nr[p][i].size()-1 ];
				nr[p][i].pop_back();

				back( l+1, maxc + ax, i );

				nr[p][i].push_back( ax );
			}
		}
	}
}

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() )
				sort( nr[i][j].begin(), nr[i][j].end(), cmpf2 );

	while ( m )
	{
		m--;
		scanf("%d %d", &k, &p);
		costmax = 0;
		back(1, 0, 0);
		if ( costmax == 0 )
			printf("-1\n");
		else	printf("%d\n", costmax );
	}

	fclose(stdin);
	fclose(stdout);

	return 0;
}