// O(P^2 * K * N)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

#define NM 300005

int N, M, NN;

int buline[NM], nbuline[101];
long long res[2][6][21], fres[21][6][21];

vector <int> lista[21];

void set_minus_one(int u, int p)
{
	for (int k = 0; k <= 5; ++k)
		for (int r = 0; r < p; ++r) res[u][k][r] = -1;
}

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", &buline[i]);
	
	for (int P = 2; P <= 20; ++P)
	{
		for (int r = 0; r < P; ++r) lista[r].clear();
		for (int i = 1; i <= N; ++i) lista[buline[i]%P].push_back(buline[i]);
		for (int r = 0; r < P; ++r) sort (lista[r].begin(), lista[r].end());
		
		NN = 0;
		
		for (int r = 0; r < P; ++r) 
		{	
			int sz = lista[r].size();
			
			for (int i = sz - 1; i >= 0 && i >= sz - 5; --i) nbuline[++NN] = lista[r][i];
		}	
		
		set_minus_one(0, P);
		
		res[0][0][0] = 0;
		
		for (int i = 1; i <= NN; ++i)
		{
			int cur = i % 2;
			int prev = !cur;
			
			memcpy (res[cur], res[prev], sizeof(res[cur]));
			
			for (int k = 0; k < 5; ++k)
				for (int r = 0; r < P; ++r)
					if (res[prev][k][r] > -1)
						res[cur][k+1][(r+nbuline[i])%P] = 
						max (res[cur][k+1][(r+nbuline[i])%P], res[prev][k][r] + nbuline[i]);
		}

		memcpy(fres[P], res[NN%2], sizeof(fres[P]));
	}	
	
	while (M--)
	{
		int k, p;
		
		scanf ("%d %d", &k, &p);
		
		printf ("%lld\n", fres[p][k][0]);
	}	
	
	return 0;
}