#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;

LL 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];
LL n,m,i,j,k,p,kk,tot;
//int b[Kmax][Pmax];
int cmp(int A,int B){
	return A>B ? 1 : 0;
}

void vezi(int k){
	LL i,s=0, vv[Pmax];
   for(i=1;i<k;++i) s+=sol[i];
   sol[k] = (p - s % p) % p;
  // for(i=k+1;i<=5;++i) sol[i]=-1;

   memset(vv,0,sizeof(vv));
   for(i=1;i<=k;++i) vv[sol[i]]++;

   for(i=0,s=0;i<p;++i)
     for(j=1;j<=vv[i];++j)
       s += a[p][i][j];
   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 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,cmp);
   for(p=2;p<=20;++p)
     for(i=1;i<=n;++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;
      back(1);
      if(tot) printf("%lld\n",tot);
      else printf("%lld\n",-1);
   }
   fclose(stdin); fclose(stdout);
   return 0;
}