// 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) 
		{	
			int r = buline[i] % P;
			lista[r].push_back(buline[i]);
			
			int j = lista[r].size() - 1;
			
			while (j && lista[r][j] > lista[r][j-1])
			{
				int aux = lista[r][j];
				lista[r][j] = lista[r][j-1];
				lista[r][j-1] = aux;
				--j;
			}	
			
			if (lista[r].size() > 5) lista[r].pop_back();
		}	
		
		NN = 0;
		
		for (int r = 0; r < P; ++r) for (int i = 0; i < lista[r].size(); ++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;
}