#include <stdio.h>
#include <string.h>
#include <algorithm>
#define Nmax 300001
#define Mmax 101
#define Kmax 6
#define Pmax 21
#define LL long long
using namespace std;

int a[Pmax][Pmax][Kmax]; // a[i][j]= nr de nr care la imp prin i dau rest j in ordine descresc
int v[Nmax],sol[Kmax];
int n,m,i,j,k,p,kk;
LL tot;
//int b[Kmax][Pmax];
int cmp(int A,int B){
	return A>B ? 1 : 0;
}

void vezi(int k){
	LL s=0; int i,lg[Pmax];
   for(i=1;i<k;++i) s+=sol[i];
   sol[k] = (p - s % p) % p;
   
   s=0; memset(lg,0,sizeof(lg));
   for(i=1;i<=k;++i)
    if(a[p][sol[i]][++lg[sol[i]]]) s+=a[p][sol[i]][lg[sol[i]]];
    else{ s=-1; break; }
   if(s > tot) tot=s;

}

void back(int k){
	int i;
	if(k > kk-1){
           // vezi(k);
	LL s=0; int ii,lg[Pmax];
           for(ii=1;ii<k;++ii) s+=sol[ii];
            sol[k] = (p - s % p) % p;
   
            s=0; memset(lg,0,sizeof(lg));
             for(ii=1;ii<=k;++ii)
             if(a[p][sol[ii]][++lg[sol[ii]]]) s+=a[p][sol[ii]][lg[sol[ii]]];
             else{ s=-1; break; }
             if(s > tot) tot=s;
   }
   else
   for(i=0;i<p;++i){
   	sol[k]=i;
      back(k+1);
   }
}

int main(){
	freopen("tricouri.in","r",stdin);
   freopen("tricouri.out","w",stdout);
   scanf("%d%d",&n,&m);
   for(i=1;i<=n;++i) scanf("%d",&v[i]);

   sort(v+1,v+n+1);
   for(p=2;p<=20;++p)
     for(i=n;i>=1;--i)
       if(a[p][v[i]%p][0] < 5)
         a[p][v[i]%p][++a[p][v[i]%p][0]]=v[i];

   for(i=1;i<=m;++i){
   	scanf("%d%d",&kk,&p);
      tot=-1;
      memset(sol,0,sizeof(sol));
      back(1);
      if(tot) printf("%lld\n",tot);
      else printf("-1\n");
   }
   fclose(stdin); fclose(stdout);
   return 0;
}