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

#include <iostream>
#include <string>

using namespace std;

#define NM 300005

int N, M;

long long buline[NM], res[2][6][21], fres[21][6][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)
	{
		set_minus_one(0, P);
		
		res[0][0][0] = 0;
		
		for (int i = 1; i <= N; ++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+buline[i])%P] = 
						max (res[cur][k+1][(r+buline[i])%P], res[prev][k][r] + buline[i]);
		}

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