#include <cstdio>
using namespace std;

const char iname[] = "tricouri.in";
const char oname[] = "tricouri.out";

#define MAX_P 21
#define MAX_K 5

int D[MAX_P][MAX_P][MAX_K];

int cnt[MAX_P][MAX_P];

int N, M, K, P;


void sort(int A[], int n) 
{
	for (int i = 0; i < n; ++ i)
		for (int j = i + 1; j < n; ++ j)
			if (A[i] < A[j])
				A[i] ^= A[j] ^= A[i] ^= A[j];
}

void insert(int i, int num)
{
	int j = num % i;
	if (cnt[i][j] < 5)
		D[i][j][cnt[i][j] ++] = num;
	else
		D[i][j][4] = num;
	sort(D[i][j], cnt[i][j]);
}

int R[MAX_K], V[MAX_P], Res;

void f(const int k)
{
	if (k == K - 1) {
		int sum = 0;
		for (int i = 0; i < K - 1; ++ i)
			sum = sum + R[i];
		if (sum == 0)
			R[k] = 0;
		else
			R[k] = P - (sum % P);
		for (int i = 0; i < P; ++ i)
			V[i] = 0;
		sum = 0;
		for (int i = 0; i < K; ++ i) {
			if (V[R[i]] < cnt[P][R[i]])
				sum = sum + D[P][R[i]][V[R[i]] ++];
			else {
				sum = -1;
				break ;
			}
		}
		if (Res < sum)
			Res = sum;
		return ;
	} 
	for (R[k] = 0; R[k] < P; R[k] ++) 
		f(k + 1);
}

int main(void)
{
	freopen(iname, "r", stdin);
	scanf("%d", & N);
	scanf("%d", & M);
	
	for (int i = 0; i < N; ++ i) {
		int num;
		scanf("%d", & num);
		for (int j = 2; j < MAX_P; ++ j)
			insert(j, num);
	}
	freopen(oname, "w", stdout);
	for (; M --; ) {
        Res = -1;
		scanf("%d %d", & K, & P);
		f(0);
		printf("%d\n", Res);
	}
	return 0;
}