#include <stdio.h>
#include <string.h>

#define NMAX 300010

int N, M;

int a[NMAX];

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 <= N; i++) {
		mod = a[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 main()
{
	int i, p;
	
	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++) 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;
}