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

#define MAX_N 300010

int n, l;
int v[MAX_N];
int d[2][32][8];

void solve(int nr, int r) {
    memset(d, 0, sizeof(d));
	l = 0;

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= r; j++)
			for (int k = 0; k <= nr; k++) 
				if (d[l][j][k] || (i == 1 && !j && !k)) {
					if (d[1 - l][j][k] < d[l][j][k])
						d[1 - l][j][k] = d[l][j][k];
					if (k < nr && d[1 - l][(j + v[i]) % r][k + 1] < d[l][j][k] + v[i])
						d[1 - l][(j + v[i]) % r][k + 1] = d[l][j][k] + v[i];

					d[l][j][k] = 0;
				}
		l = 1 - l;
	}	

	if (!d[l][0][nr]) d[l][0][nr] = -1;
	printf("%d\n", d[l][0][nr]);
}

int main() {

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

	int t;
	scanf("%d %d", &n, &t);
	for (int i = 1; i <= n; i++)
		scanf("%d", &v[i]);

	while (t--) {
		int k, p;

		scanf("%d %d", &k, &p);
		solve(k, p);
	}

	return 0;
}