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

using namespace std;

const int N_MAX = 300010;
const int P_MAX = 23;
const int K_MAX = 8;

int is[P_MAX][K_MAX], is2[P_MAX][K_MAX];

int v2[N_MAX], v[P_MAX * K_MAX], cnt[P_MAX], prec[P_MAX][K_MAX];

int main()
{
	freopen("tricouri.in", "r", stdin);
	freopen("tricouri.out", "w", stdout);
	
	int N, M, K, P, j, k, i, nr, sum, S;
	scanf("%d %d\n", &N, &M);
	for (i = 1; i <= N; i ++) {
		scanf("%d ", &v2[i]);
	}
	sort(v2 + 1, v2 + N + 1);

	for (P = 2; P <= 20; P ++) {
		memset(cnt, 0, sizeof(cnt));

		v[0] = 0;
		for (i = N; i >= 1; i --) {
			if (cnt[v2[i] % P] < 5) {
				v[++ v[0]] = v2[i];
				cnt[v2[i] % P] ++;
			}
		}

		memset(is, 0, sizeof(is));

		S = v[1] % P;
		is[S][1] = v[1];
		is[S][0] = 1;
		for (i = 2; i <= v[0]; i ++) {
			nr = v[i] % P;
			if (v[i] > is2[nr][1]) {
				is2[nr][1] = v[i];
				is2[nr][0] = 1;
			}

			for (j = P - 1; j >= 0; j --) {
				if (is[j][0]) {
					sum = (j + nr) % P;
					for (k = 5; k >= 1; k --) {
						if (k + 1 <= 5) {
							if (is[j][k] + v[i] > is2[sum][k + 1]) {
								is2[sum][k + 1] = is[j][k] + v[i];
								is2[sum][0] = 1;
							}
						}
					}
				}
			}

			for (j = 0; j <= P; j ++) {
				for (k = 0; k <= 5; k ++) {
					if (is2[j][k] > is[j][k]) {
						is[j][k] = is2[j][k];
					}
					is2[j][k] = 0;
				}
			}
		}

		for (i = 1; i <= 5; i ++) {
			prec[P][i] = is[0][i];
		}
	}

	for (; M; M --) {
		scanf("%d %d\n", &K, &P);
		if (prec[P][K]) {
			printf("%d\n", prec[P][K]);
		} else {
			printf("-1\n");
		}
	}
	
	return 0;
}