#include <cstdio>
#include <algorithm>
#define NMax 300000
#define VMax 20
#define TMax 5
using namespace std;

int ans[TMax+1][VMax+1];
int dp[VMax+1][TMax+1];
int a[VMax+1];
int v[NMax+1];
int P,K,N;

void Verif()
{
    int i,r,rez;

    int t[VMax+1];
    for(i = 0; i <= VMax; ++i) t[i] = 1;

    for(rez = r = 0, i = 1; i <= K; ++i)
    {
        r = r + a[i];
        rez = rez + dp[ a[i] ][ t[ a[i] ]++ ];
    }
    if( !(r%P) && rez > ans[K][P] ) ans[K][P] = rez;
}

void Gen(int k)
{
    if(k==K+1) Verif();
    else
    {
        for(int i = a[k-1]; i < P; ++i)
        if( dp[i][0] )
        {
            a[k] = i;
            Gen(k+1);
        }
    }
}

void Precalc()
{
    int i,j;

    for(P = 2; P <= VMax; ++P)
    {
        for(i = 0; i <= VMax; ++i)
            for(j = 0; j <= TMax; ++j) dp[i][j] = 0;

        for(i = N; i >= 1; --i)
        if( dp[ v[i]%P ][0] < 5 ) dp[ v[i]%P ][ ++dp[ v[i]%P ][0] ] = v[i];

        for(K = 1; K <= TMax; ++K) Gen(1);
    }
}

int main(){
    freopen("tricouri.in","r",stdin);
    freopen("tricouri.out","w",stdout);

    int i,M;

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

    Precalc();
    for(i = 1; i <= M; ++i)
    {
        scanf("%d %d",&K,&P);
        if( !ans[K][P] ) printf("-1\n");
        else printf("%d\n", ans[K][P] );
    }



return 0;
}