#include <stdio.h>
#define INF 666000666
#define NMAX 26

int A[NMAX][NMAX][6], V[300003], G[NMAX], N, M, K, P, Smax;

void back(int nv)
{
        int i, g[NMAX], s, v, mod;
        if (nv==K)
        {
                for (i = 0; i < NMAX; i++) g[i] = 0;
                for (i = 1, s = v = 0; i < K; i++){
                    if (!A[P][G[i]][g[G[i]]]) { s=-1; break; }
                    s += A[P][G[i]][g[G[i]]++]; v+=G[i];}
                mod = (P-v%P)%P;
                if (s>=0)
                {
                   if (A[P][mod][g[mod]]) s += A[P][mod][g[mod]];
                   else s = -1;
                }
                if (s>Smax) Smax = s;
                return;
        }

        for (i = 0; i < P; i++)
        {
                G[nv] = i;
                back(nv+1);
        }
}

int main()
{
        int i, j, k, t, min, pmin=0, mod, g[NMAX], aux;
        freopen("tricouri.in", "r", stdin);
        scanf("%d%d", &N, &M);
        for (i = 0; i < N; i++) scanf("%d", V+i);


        for (i = 2; i <= 20; i++)
        {
            for (j = 0; j < NMAX; j++) g[j] = 0;
            for (j = 0; j < N; j++)
            {
                mod = V[j]%i;
                if (g[mod]<5) A[i][mod][ g[mod]++ ] = V[j];
                else
                {
                        for (k = pmin = 0, min = INF; k < 5; k++)
                            if (min>A[i][mod][k]) min = A[i][mod][k], pmin = k;
                        A[i][mod][pmin] = V[j];
                }
            }
         }
         
        for (i = 2; i <= 20; i++)
            for (j = min = 0; j < 20; j++)
                for (k = 0; k < 5; k++)
                    for (t = k+1; t < 5; t++)
                        if (A[i][j][k]<A[i][j][t])
                           aux = A[i][j][k], A[i][j][k] = A[i][j][t], A[i][j][t] = aux;

        freopen("tricouri.out", "w", stdout);
        while (M--)
        {
                scanf("%d%d", &K, &P);
                Smax = -1;
                back(1);
                printf("%d\n", Smax);
        }

        return 0;
}