#include <stdio.h>
#include <algorithm>

using namespace std;

int mat[21][20][6], n, m, sol = -1, k, p, sum, nr;

bool cmp(int one, int two)
{
	return one > two;
}

void bkt(int pos);
int main()
{
	freopen("tricouri.in","r",stdin);
	freopen("tricouri.out","w",stdout);
	
	int a, i, j, temp;
	
	scanf("%d%d", &n, &m);
	
	for(i = 1; i <= n; ++i)
	{
		scanf("%d", &a);
		for(j = 1; j <= 20; ++j)
		{
			temp = a % j;
			if(a > mat[j][temp][5])
			{
				++mat[j][temp][0];
				mat[j][temp][5] = a;
				sort(mat[j][temp] + 1, mat[j][temp] + 6, cmp);
			}
		}
	}
	for(i = 1; i <= m; ++i)
	{
		sol = 0;
		scanf("%d%d", &k, &p);
		bkt(0);
		if(sol == 0)
			sol = -1;
		printf("%d\n", sol);
	}	
	return 0;
}

void bkt(int pos)
{
	int i, j;
	if(pos == p)
	{
		if(nr == k && sum % p == 0)
		{
			if(sum > sol)
			{
				sol = sum;
			}
		}
	}
	else
	{
		bkt(pos + 1);
		for(i = 1; i <= mat[p][pos][0] && nr + i <= k; ++i)
		{
			for(j = 1; j <= i; ++j)
			{
				sum += mat[p][pos][j];
				++nr;
			}
				bkt(pos + 1);
			for(j = 1; j <= i; ++j)
			{
				sum -= mat[p][pos][j];
				--nr;
			}
		}
	}
}