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

#define MAX 300010
#define INF 10000010
#define pb push_back

using namespace std;

int n, m;
int el[MAX];
int vctEl[32][32], pos[32][32], sol[32][32];

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", &el[i]);

	for (int p = 2; p <= 20; p++)
	{
		for (int r = 0; r < p; r++)
			for (int t = 0; t <= 5; t++)
				pos[r][t] = -INF;
		vector <int> vctNr;
		memset(vctEl, 0, sizeof(vctEl));

		for (int i = 1; i <= n; i++)
		{
			int loc = el[i] % p;
			vctEl[loc][++vctEl[loc][0]] = el[i];
			
			for (int j = vctEl[loc][0]; j > 1; j--)
				if (vctEl[loc][j] > vctEl[loc][j - 1])
					swap(vctEl[loc][j], vctEl[loc][j - 1]);
				
			if (vctEl[loc][0] > 5)
				vctEl[loc][0]--;
		}
		
		vctNr.pb(0);
		for (int r = 0; r < p; r++)
			for (int i = 1; i <= vctEl[r][0]; i++)
				vctNr.pb(vctEl[r][i]);

		int nr = vctNr.size() - 1;

		pos[0][0] = 0;
		for (int el = 1; el <= nr; el++)
			for (int r = 0; r < p; r++)
				for (int t = 5; t; t--)
					pos[(r + vctNr[el]) % p][t] = max(pos[(r + vctNr[el]) % p][t], pos[r][t - 1] + vctNr[el]);

		for (int t = 1; t <= 5; t++)
			sol[t][p] = max(-1, pos[0][t]);
	}

	for (; m; m--)
	{
		int t, r;
		scanf("%d %d", &t, &r);

		printf("%d\n", sol[t][r]);
	}

	fclose(stdin);
	fclose(stdout);
	return 0;
}