#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define NMAX 300010

int N, M, PP;

int a[NMAX];
int nb;
int b[200];

int ant[6][20];
int cur[6][20];

int mat[22][6][20];

inline int MAX(int a, int b) { return (a > b) ? a : b; }

void calc(int P)
{
	memset(ant, 0, sizeof(ant));
	memset(cur, 0, sizeof(cur));

	int i, mod, j, p, q;

	for (i = 1; i <= nb; i++) {
		mod = b[i] % P;
		for (j = 1; j <= 5; j++)
			for (p = 0; p < P; p++) {
				q = p - mod;
				if (q < 0) q += P;
				if (j == 1 && q > 0) continue;
				if (!ant[j-1][q] && j > 1) continue;

				cur[j][p] = MAX(cur[j][p], ant[j-1][q] + a[i]);
			}
		
		memcpy(ant, cur, sizeof(cur));
	}

	memcpy(mat[P], cur, sizeof(cur));
}

int cmp(int a, int b)
{
	return a % PP < b % PP;
}

int main()
{
	int i, p, j, q;
	
	freopen("tricouri.in", "r", stdin);
	freopen("tricouri.out", "w", stdout);

	scanf("%d %d", &N, &M);

	for (i = 1; i <= N; i++) scanf("%d", &a[i]);

	for (p = 2; p <= 20; p++) {
		PP = p;
		sort(a + 1, a + N + 1, cmp);

		nb = 0;
		for (i = 1; i <= N; ) {
			for (j = i; a[j] % PP == a[i] % PP; j++);

			for (q = j - 1; q >= j - 5 && q >= i; q--) b[++nb] = a[q];

			i = j;
		}

		calc(p);
	}

	int K, P;
	for (i = 1; i <= M; i++) {
		scanf("%d %d", &K, &P);

		if (!mat[P][K][0]) printf("-1\n");
		else printf("%d\n", mat[P][K][0]);
	}


fclose(stdin);
fclose(stdout);
return 0;
}