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

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], ex[P_MAX][K_MAX];

int v[N_MAX];

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

		for (i = 0; i <= P; i ++) {
			memset(is[i], 0, sizeof(is[i]));
			memset(ex[i], 0, sizeof(ex[i]));
		}

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

			mx = S;
			for (j = S; j >= 0; j --) {
				if (is[j][0]) {
					sum = (j + nr) % P;
					if (sum > S) {
						mx = sum;
					}
					for (k = K; k >= 1; k --) {
						if (k + 1 <= K && ex[j][k]) {
							if (i == N) {
							}
							if (is[j][k] + v[i] > is2[sum][k + 1]) {
								is2[sum][k + 1] = is[j][k] + v[i];
								is2[sum][0] = 1;
							}
						}
					}
				}
			}
			S = mx;

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

		if (is[0][K]) {
			printf("%d\n", is[0][K]);
		} else {
			printf("-1\n");
		}
	}
	
	return 0;
}