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

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

    if(rez==P)
    rez=0;
    
    if(nr[rez]<a[rez][0]){
    nr[rez]++;
    S+=a[rez][ nr[rez] ];
      if(S>maxx)   
      maxx=S;
    S-=a[rez][ nr[rez] ];
    nr[rez]--;
    }
  }   
  
}   
  
  
  
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;   
}