#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);else
   for(i=0;i<p;++i){
   	sol[k]=i;
      back(k+1);
   }
}
int check(){
    int i,min=1<<22,j=0;
    for(i=1;i<=5;++i)
      if(a[p][v[i]%p][i] < min) min=a[p][v[i]%p][i],j=i;
    if( v[i] > min) return j;
}      

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];
       else{
            j=check();
            if(j) a[p][v[i]%p][j]=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;
}