#include<stdio.h>   
#include<algorithm>   
using namespace std;   
#define INF 1000010
  
int viz[21],rez,nr[21],j,i,l,r,a[21][21][6],minn,k,s[6],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-1){
  
    for(i=s[x-1];i<P;i++){
  
      if(nr[i]<a[P][i][0]){
      s[x]=i;   
      nr[s[x]]++;   
      S+=a[P][i][ nr[s[x]] ] ;
      back(x+1);   
      S-=a[P][i][ nr[s[x]] ] ;
      nr[s[x]]--;   
      }   
         
    }   
  
  }   
  
  else{

  rez=S%P;
  rez=P-rez;

    if(rez==P)
    rez=0;
    
    if(nr[rez]<a[P][rez][0]){

      if(S+a[P][rez][ nr[rez]+1 ]>maxx)
      maxx=S+a[P][rez][ nr[rez]+1 ];

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

   if(!viz[P]){
    for(i=1;i<=n;i++){   
    r=v[i]%P;   
  
       if(a[P][r][0]<5){
       a[P][r][0]++;
       a[P][r][a[P][r][0]]=v[i];
       }   
  
       else{   
       minn=INF;   
  
         for(j=1;j<=5;j++)
           if(a[P][r][j]<minn){
           minn=a[P][r][j];
           p=j;   
           }   
  
         if(minn<v[i])   
         a[P][r][p]=v[i];
  
       }   
  
    }   
   }
    for(i=0;i<P;i++){
    sort(a[P][i]+1,a[P][i]+a[P][i][0]+1,cmp);
    }
  
  maxx=-1;   
  S=0;   
  back(1);   
  
    fprintf(g,"%d\n",maxx);   
       viz[P]=1;
     for(i=0;i<=P;i++){   
     nr[i]=0;
     }   
  
  }   
  
fclose(f);   
fclose(g);   
  
return 0;   
}