#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream fin ("tricouri.in");
ofstream fout ("tricouri.out");
int n,m,i,j,p,k,maxim,t,v[300001],x[10];
vector < pair<int,int> > L[21][21];
void back (int pas,int k,int p){
    if (pas == k){
        for (int i=0;i<p;i++)
            for (int j=0;j<L[p][i].size();j++)
                L[p][i][j].second = 0;
        /// calculam suma maxima;
        int nr = 0;
        int suma = 0;
        int OK = 0;
        for (int i=1;i<k;i++){
            nr += x[i];
            int ok = 0;
            for (int j=0;j<L[p][x[i]].size();j++){
                if (L[p][x[i]][j].second == 0){
                    suma += L[p][x[i]][j].first;
                    L[p][x[i]][j].second = 1;
                    ok = 1;
                    break;
                }
            }
            if (ok == 0)
                OK = 1;
        }
        int rest = p + p*(nr/p) - nr;
        int ok = 0;
        for (int j=0;j<L[p][rest].size();j++)
            if (L[p][rest][j].second == 0){
                suma += L[p][rest][j].first;
                L[p][rest][j].second = 1;
                ok = 1;
                break;
            }
        if (ok == 0)
            OK = 1;
        if (suma > maxim && OK == 0)
            maxim = suma;

        return;
    }
    for (int i=0;i<p;i++){
        x[pas] = i;
        back (pas+1,k,p);
    }
}
int main (){

    fin>>n>>m;
    for (i=1;i<=n;i++)
        fin>>v[i];
    sort (v+1,v+n+1);
    /// construim lista cu resturile
    for (i=n;i>=1;i--){
        /// nr care dau restul r la impartirea cu j
        for (j=2;j<=20;j++){
            if (L[j][v[i]%j].size() <= 5)
                L[j][v[i]%j].push_back (make_pair(v[i],0));
        }
    }
    for (;m--;){
        /// initializam cu 0
       // for (i=2;i<=20;i++)
          //  for (j=0;j<i;j++)
             //   for (t=0;t<L[i][j].size();t++)
               //     L[i][j][t].second = 0;
        fin>>k>>p;
        maxim = 0;
        back (1,k,p);
        if (maxim <= 0)
            fout<<-1<<"\n";
        else
            fout<<maxim<<"\n";
    }


    return 0;
}