#include <fstream>
	
#include <algorithm>
	
#include <cstring>
	
#define INF 2000000000
	
using namespace std;
	
int n,m,i,p,r,k,j,el,nr,v[300001],w[22],d[21][21][21],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 (k=0;k<=5;k++)
	
        for (p=2;p<=20;p++)
	
            for (r=1;r<p;r++)
	
                d[k][p][r] = -INF;
	
 
	
    for (p=2;p<=20;p++){
	
        //for (i=0;i<p;i++)
	
          //  w[i] = 0;
	
        memset (w,0,sizeof(w));
	
        el = 0;
	
        nr = 0;
	
        for (i=n;i>=1;i--){
	
            if (w[v[i]%p] < 5){
	
                w[v[i]%p]++;
	
                x[++el] = v[i];
	
                if (w[v[i]%p] == 5)
	
                    nr++;
	
            }
	
 
	
            if (nr == p)
	
                break;
	
        }
	
        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<<-1<<"\n";
	
        else
	
            fout<<d[k][p][0]<<"\n";
	
    }
	
 
	
    return 0;
	
}