#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#define PB push_back
#define MAX(a, b) ( (a) < (b) ? (b) : (a) )
#define MMAX 300001
#define NMAX 25
#define PMAX 20
#define KMAX 5

using namespace std;

int A[NMAX][NMAX][KMAX + 1];
int S[NMAX][NMAX][KMAX + 1];
int V[MMAX], St[NMAX], U[NMAX];
int i, j, k, N, M;
int K, P, maxs;

void back(int i)
{
	int k, j;
	
	if (i > K - 1)
	{
		int sm = 0, OK = 1, suma = 0;
		
		memset(U, 0, sizeof(U));
		
		for (j = 1; j <= K - 1; j++) sm += St[j], U[St[j]]++;
		
		for (j = 0; j < P; j++) if ((sm + j) % P == 0) break;
		
		St[K] = j, U[St[K]]++;
		
		//for (j = 1; j <= K; j++) printf("%d ", St[j]);
		
		//printf("\n");
		
		for (j = 0; j < P; j++) 
			if (U[j] > A[P][j][0]) { OK = 0; break; }
		
		if (OK)
		{
			for (j = 0; j < P; j++) suma += S[P][j][U[j]];
			
			maxs = MAX(maxs, suma);
		}
		
	}
	else
	{
		for (k = 0; k < P; k++)
		{
			St[i] = k;
			back(i + 1);
			St[i] = -1;
		}
	}
}

int main()
{
	freopen("tricouri.in", "r", stdin);
	freopen("tricouri.out", "w", stdout);
	
	scanf("%d %d", &N, &M);
	
	for (i = 1; i <= N; i++) scanf("%d", &V[i]);
	
	sort(V + 1, V + N + 1);
	
	for (i = N; i >= 1; i--)
	{
		for (j = 2; j <= PMAX; j++)
				if (A[j][V[i] % j][0] < KMAX) A[j][V[i] % j][ ++A[j][V[i] % j][0] ] = V[i];
	}
	
	for (i = 2; i <= PMAX; i++)
		for (j = 0; j <= i - 1; j++)
		{
			//printf("%d %d -\n", i, j);
			
			for (k = 1; k <= A[i][j][0]; k++)
			{
				//printf("%d ", A[i][j][k]);
				S[i][j][k] = S[i][j][k-1] + A[i][j][k];
				//printf("%d    ", S[i][j][k]);
			}
			
			//printf("\n");
		}
	
		
		
	for (i = 1; i <= M; i++)
	{
		for (j = 0; j < NMAX; j++) St[j] = -1;
		
		maxs = -1;
		
		scanf("%d %d", &K, &P);
		
		back(1);
		
		printf("%d\n", maxs);
	}		
			 
		
	return 0;
	
}