#include <fstream>
#include <algorithm>
#define INF 2000000000
using namespace std;
int n,m,i,p,r,k,j,el,nr,v[300001],w[300001],d[21][21][7],x[300001];
ifstream fin ("tricouri.in");
ofstream fout ("tricouri.out");

int main (){

    fin>>n>>m;
    for (i=1;i<=n;i++)
        fin>>v[i];
    sort (v+1,v+n+1);
    for (p=2;p<=20;p++)
        for (r=1;r<p;r++)
            for (k=0;k<=5;k++)
                d[k][p][r] = -INF;

    for (p=2;p<=20;p++){
        for (i=0;i<p;i++)
            w[i] = 0;
        el = 0;
        nr = 0;
        for (i=n;i>=1;i--){
            if (w[v[i]%p] < 5){
                w[v[i]%p]++;
                x[++el] = v[i];
                continue;
            }
            /// inseamna ca w[v[i]%p] == 5
            if (w[v[i]%p] == 5)
                nr++;
            if (nr == p)
                break; /// am completat toate listele
        }
        for (i=1;i<=el;i++)
            for (k=4;k>=0;k--)
                for (r=0;r<p;r++)
                    d[k+1][p][(r+x[i])%p] = max (d[k+1][p][(r+x[i])%p],d[k][p][r] + x[i]);
    }

    for (i=1;i<=m;i++){
        fin>>k>>p;
        if (d[k][p][0] > 0)
            fout<<d[k][p][0]<<"\n";
        else
            fout<<-1<<"\n";
    }

    return 0;
}