#include<stdio.h>
#include<algorithm>
using namespace std;
#define INF 1000100

int ii,nr[30],j,i,l,r,a[21][30],minn,k,s[30],p,S,v[300010],P,maxx,n,m;

int cmp(int a,int b){
return a>b;
}

void back(int x){
int i;

  if(x<=k){

    for(i=s[x-1];i<P;i++){

      if(nr[i]<a[i][0]){
      s[x]=i;
      nr[s[x]]++;
      S+=a[i][ nr[s[x]] ] ;
      back(x+1);
      S-=a[i][ nr[s[x]] ] ;
      nr[s[x]]--;
      }
      
    }

  }

  else{

    if(S==0|| (S%P==0) ){
      if(S>maxx)
      maxx=S;
    }

  }

}



int main(){


FILE *f=fopen("tricouri.in","r");
FILE *g=fopen("tricouri.out","w");

fscanf(f,"%d %d",&n,&m);

  for(i=1;i<=n;i++){
  fscanf(f,"%d",&v[i]);
  }

  for(l=1;l<=m;l++){
  fscanf(f,"%d %d",&k,&P);
  
    for(i=1;i<=n;i++){
    r=v[i]%P;

       for(j=k;j>=1;j--){
         if(j==1)
         break;

         if(v[i]<a[r][j]){
         j++;
         break;
         }
         
       }

         if(j!=k){

           for(ii=a[r][0];ii>=j;ii--){
           a[r][ii+1]=a[r][ii];
           }

         a[r][j]=v[i];
           if(a[r][0]<k)
           a[r][0]++;

         }
    }

  maxx=-1;
  S=0;
  back(1);

    fprintf(g,"%d\n",maxx);

     for(i=0;i<=P;i++){
     a[i][0]=0;
     nr[i]=0;
     }

  }

fclose(f);
fclose(g);

return 0;
}