#include <cstdio>
#include <algorithm>
#define MAXN 300000
#define MAXK 5
#define MAXP 20
using namespace std;
long long d[2][MAXK+1][MAXP+1][MAXP+1];
int v[MAXN+1],vf[MAXP+1],v1[MAXP*MAXP*MAXK+1];
inline long long getmax(long long a,long long b){
    if(a>b) return a;
    return b;
}
int main(){
    FILE*fi,*fout;
    int i,j,n,m,k,r,p,x;
    fi=fopen("tricouri.in" ,"r");
    fout=fopen("tricouri.out" ,"w");
    fscanf(fi,"%d%d" ,&n,&m);
    for(i=1;i<=n;i++)
        fscanf(fi,"%d" ,&v[i]);
    sort(v+1,v+n+1);
    x=0;
    for(p=1;p<=20;p++){
      for(i=n;i>0;i--)
        if(vf[v[i]%p]<5&&v[i]>0){
           v1[++x]=v[i];
           vf[v[i]%p]++;
           v[i]=0;
        }
        for(i=0;i<p;i++)
           vf[i]=0;
    }
    k=5;
    for(p=1;p<=20;p++)
     for(i=1;i<=x;i++)
       for(j=1;j<=k;j++)
         for(r=0;r<p;r++)
          if(d[1-i&1][j-1][r][p]%p==r)
           d[i&1][j][(r+v1[i])%p][p]=getmax(d[1-i&1][j][(r+v1[i])%p][p],getmax(d[1-i&1][j-1][r][p]+v1[i],d[i&1][j][(r+v1[i])%p][p]));
          else
           d[i&1][j][(r+v1[i])%p][p]=getmax(d[1-i&1][j][(r+v1[i])%p][p],d[i&1][j][(r+v1[i])%p][p]);
    while(m>0){
        m--;
        fscanf(fi,"%d%d" ,&k,&p);
        if(d[m&1][k][0][p]==0)
              fprintf(fout,"-1\n");
        else
              fprintf(fout,"%lld\n" ,d[n&1][k][0][p]);
    }
    fclose(fi);
    fclose(fout);
    return 0;
}