#include<cstdio>
#include<set>
using namespace std;
multiset <int> a[21][21];
int k,p,sum;
int bkt(int k){
  if(k==1){
    int r;
    r=p-sum%p;
    multiset <int>::iterator it;
    if(!a[r][p].empty()){
      it=a[r][p].end();
      it--;
      return sum+*it;
    }else
      return -1;
  }else{
    int maxi=-1,el,i,nr;
    multiset <int>::iterator it;
    for(i=0;i<p;i++){
      if(!a[i][p].empty()){
        it=a[i][p].end();
        it--;
        el=*it;
        sum+=el;
        a[i][p].erase(it);
        nr=bkt(k-1);
        if(nr>maxi)
          maxi=nr;
        sum-=el;
        a[i][p].insert(el);
      }
    }
    return maxi;
  }
}
int main(){
  int n,m,i,x,j;
  freopen("tricouri.in","r",stdin);
  freopen("tricouri.out","w",stdout);
  scanf("%d%d",&n,&m);
  for(i=1;i<=n;i++){
    scanf("%d",&x);
    for(j=2;j<=20;j++){
      a[x%j][j].insert(x);
      if(a[x%j][j].size()>5)
        a[x%j][j].erase(a[x%j][j].begin());
    }
  }
  for(i=1;i<=m;i++){
    scanf("%d%d",&k,&p);
    printf("%d\n",bkt(k));
  }
  return 0;
}