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

#define NMAX 300002

int N, M;

int a[NMAX];
int nb;
int b[110];
int nrm[22];

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] + b[i]);
			}
		
		memcpy(ant, cur, sizeof(cur));
	}

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

int main()
{
	int i, p, 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]);

	sort(a + 1, a + N + 1);

	for (p = 2; p <= 20; p++) {
		nb = 0;
		memset(nrm, 0, sizeof(nrm));
		for (i = N; i >= 1; i--) {
			q = a[i] % p;
			if (nrm[q] < 5) {
				nrm[q]++;
				b[++nb] = a[i];
			}
		}

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