#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int NMAX = 300001;
const int PMAX = 21;
const int VMAX = 5;
const int KMAX = 6;
const int INF = 0x3f3f3f3f;

int N, M;
int A[NMAX];
int D[PMAX][PMAX][VMAX];
int ND[PMAX][PMAX];
int DP[PMAX][KMAX][PMAX][PMAX];

int dinamica(int P, int k, int l, int rest) {
	if (l == 0)
		if (rest == 0) return 0; else return -INF;
	
	if (DP[P][k][l][rest] != -1) return DP[P][k][l][rest];

	int &rez = DP[P][k][l][rest], s, i, j;
	rez = -INF;
	
	for (i = 0; i < k; ++i) {
		s = 0;
		for (j = 0; j < l && j < ND[P][i]; ++j) {
			s += D[P][i][j];
			rez = max(rez, s + dinamica(P, i, l - j - 1, (rest + i * (j + 1)) % P));
		}
	}

//	printf("%d %d %d %d => %d\n", P, k, l, rest, rez);

	return rez;
}

int main() {
	FILE *fin = fopen("tricouri.in", "rt");
	FILE *fout = fopen("tricouri.out", "wt");
	int i, j, r, k;

	fscanf(fin, " %d %d", &N, &M);

	for (i = 0; i < N; ++i)
		fscanf(fin, " %d", A + i);
	
	sort(A, A + N);

	for (i = N - 1; i >= 0; --i) {
		
		for (j = 1; j < PMAX; ++j) {
			r = A[i] % j;

			if (ND[j][r] < VMAX)
				D[j][r][ND[j][r]++] = A[i];
		}
	}

	memset(DP, 0xff, sizeof(DP));

	for (i = 0; i < M; ++i) {
		fscanf(fin, " %d %d", &k, &j);

		r = dinamica(j, j, k, 0);
		fprintf(fout, "%d\n", r >= 0 ? r : -1 );
	}

	fclose(fin);
	fclose(fout);
	return 0;
}