#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX(a, b) ( (a) < (b) ? (b) : (a) )
#define MMAX 300001
#define NMAX 21
#define PMAX 20
#define KMAX 5
 
using namespace std;
 
int A[NMAX][NMAX][KMAX + 1];
int V[MMAX];
int i, j, k, N, M;
int K, P, maxs, sum, aux, rest;
 
void back(int i, int r)
{
    int k;
     
    if (i > K - 1)
    {
        k = (4 * P - rest) % P;
         
        aux = sum + A[P][k][A[P][k][0]];
         
        maxs = MAX(maxs, aux);
    }
    else
    for (k = r; k < P; k++)
        if (A[P][k][A[P][k][0]] >= 0)
        {
               sum += A[P][k][A[P][k][0]];
               A[P][k][0]++;
               rest += k;
                
               back(i+1, k);
                
               A[P][k][0]--;
               sum -= A[P][k][A[P][k][0]];
               rest -= k;
        }
}
 
int main()
{
    freopen("tricouri.in", "r", stdin);
    freopen("tricouri.out", "w", stdout);
     
    scanf("%d %d", &N, &M);
     
    for (i = 0; i < NMAX; i++)
        for (j = 0; j < NMAX; j++)
            for (k = 1; k <= KMAX; k++)  A[i][j][k] = -1;
     
    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)
                {
                    k = V[i] % j;
                     
                    int nr = ++A[j][k][0];
                     
                    A[j][k][nr] = V[i];
                }
    }
     
    for (i = 1; i <= M; i++)
    {       
        maxs = -1, sum = 0, rest = 0;
         
        scanf("%d %d", &K, &P);
         
        for (j = 0; j < P; j++) A[P][j][0] = 1; 
         
        back(1, 0);
         
        printf("%d\n", maxs);
    }       
              
         
    return 0;
     
}