#include <cstdio>
#include <algorithm>

using namespace std;

#define MAXN 300005
#define MAXK 6
#define MAXP 21

int N, M, P, K;
int x[MAXN];
int Maxnr[MAXP + 1][MAXK + 1], l[MAXP + 1];
int Max[MAXP + 1][MAXK + 1];
int st[MAXK + 1];

int cmp( int a, int b ) { return a > b; }

void back(int k, int Sr, int S)
{
	if (k == K)
	{
		if (Sr != 0)
			return;
		if (S > Max[P][K])
			Max[P][K] = S;
		return;
	}
	int i = 0;
	if (k)
		i = st[k - 1];
	for (; i < P; i++)
	{
		if (l[i] > Maxnr[i][0])
			continue;

		l[i]++;
		st[k] = i;
		back(k + 1, (Sr + i) % P, S + Maxnr[i][ l[i] - 1 ]);
		l[i]--;
	}
}

int main()
{
	freopen("tricouri.in", "rt", stdin);
	freopen("tricouri.out", "wt", stdout);
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++)
		scanf("%d", x + i);
	sort(x, x + N, cmp);

	for (P = 1; P < MAXP; P++)
	{
		for (int i = 0; i < P; i++)
			Maxnr[i][0] = 0,
			l[i] = 1;

		for (int i = 0; i < N; i++)
		{
			if (Maxnr[ x[i] % P ][0] == MAXK - 1)
				continue;
			Maxnr[ x[i] % P ][ ++Maxnr[ x[i] % P ][0] ] = x[i];
		}

		for (K = 1; K < MAXK; K++)
		{
			Max[P][K] = -1;
			back(0, 0, 0);
		}
	}

	for (; M; M--)
	{
		int p, k;
		scanf("%d %d", &k, &p);
		printf("%d\n", Max[p][k]);
	}
	return 0;
}