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

using namespace std;

#define MAX_N 300010
#define L 32

int n, m, k, p;
int A[MAX_N];
int v[L][L][8], ind[L][L], sum[8][L], c[8][L];
int nr[128];

void prec() {
	for (int i = n; i >= 1; i--)
		for (int j = 2; j <= 20; j++) {
            int r = A[i] % j;
        	
			if (ind[j][r] < 5) v[j][r][++ind[j][r]] = A[i];
		}

	for (int rest = 2; rest <= 20; rest++) {
		nr[0] = 0;
		for (int i = 0; i < rest; i++)
			for (int j = 1; j <= ind[rest][i]; j++)
				nr[++nr[0]] = v[rest][i][j];
		
		memset(c, 0, sizeof(c));

		for (int i = 1; i <= nr[0]; i++)
			for (int j = 4; j >= 0; j--)
				for (int k = 0; k < rest; k++)
        			if (c[j][k] > 0 || (!j && !k))
						if (c[j][k] + nr[i] > c[j + 1][(k + nr[i]) % rest])
							c[j + 1][(k + nr[i]) % rest] = c[j][k] + nr[i];

		for (int i = 1; i < 6; i++) {
			sum[i][rest] = -1;
			if (c[i][0]) sum[i][rest] = c[i][0];
		}
	}
}

int main() {

	freopen("tricouri.in", "r", stdin);
	freopen("tricouri.out", "w", stdout);

	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%d", &A[i]);
	sort(A + 1, A + n + 1);

	prec();

	for (int i = 1; i <= m; i++) {
    	scanf("%d %d", &k, &p);
		printf("%d\n", sum[k][p]);
	}

	return 0;
}