#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAXN 300002
#define MAX(a,b) ((a) > (b) ? (a) : (b))

int N, M, V[MAXN];
int K, P, smax;

int x[32], cnt[32], A[32][32][6], deg[32][32];

void preproc(void)
{
    int i, p, r;

    sort(V+1, V+N+1);

    for(p = 2; p <= 20; p++)
     for(i = N; i >= 1; i--)
      if(deg[p][ r = V[i]%p ] < 5)
        A[p][r][ ++deg[p][r] ] = V[i];

}

void bkt(int k, int mod)
{
    int i, s;
    
    if(k == K)
    {
        x[k] = (P-mod == P ? 0 : P-mod);
        for(s = 0, i = 1; i <= K; i++)
         if(cnt[x[i]] < deg[P][x[i]])
            cnt[x[i]]++, s += A[P][x[i]][ cnt[x[i]] ];
         else
            break ;

        if(i == K+1)
            smax = MAX(smax, s);
            
        for(i = 1; i <= K; i++)
            cnt[x[i]] = 0;
    }
    else
        for(i = 0; i < P; i++)
        {
            x[k] = i;
            if(mod+i >= P)
                bkt(k+1, mod+i-P);
            else
                bkt(k+1, mod+i);
        }
}

void read_and_solve(void)
{
    int i;

    scanf("%d %d\n", &N, &M);

    for(i = 1; i <= N; i++)
        scanf("%d ", &V[i]);

    preproc();

    for(i = 1; i <= M; i++)
    {
        scanf("%d %d\n", &K, &P), smax = -1;
        bkt(1, 0);
        printf("%d\n", smax);
    }
}

int main(void)
{
    freopen("tricouri.in", "rt", stdin);
    freopen("tricouri.out", "wt", stdout);

    read_and_solve();

    return 0;
}