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

int nr[20],j,i,l,r,a[20][10],minn,k,s[10],p,S,v[300100],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;

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

       else{
       minn=INF;

         for(j=1;j<=k;j++)
           if(a[r][j]<minn){
           minn=a[r][j];
           p=j;
           }

         if(minn<v[i])
         a[r][p]=v[i];

       }

    }

    for(i=0;i<P;i++){
    sort(a[i]+1,a[i]+a[i][0]+1,cmp);
    }

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