#include<stdio.h>   
#include<algorithm>   
using namespace std;   
#define INF 1000100   
  
int nr[21],j,i,l,r,a[21][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;   
}  
#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;
}