#include<stdio.h>

int max,ss,q,nr,ok,S,s[300011],c,aux,p,n,N,M,i,x,j,l,m[22][22][10],min,k,d;

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


int back(int k){
int i;

  if(k<=c){

     for(i=s[k-1];i<=d-1;i++){

      if(m[d][i][0]){
      s[k]=i;


	back(k+1);
      }



     }


  }


  else{
  ss=0;

  for(j=1;j<=c;j++)
   ss+=s[j];


  if(ss%d==0){

  ok=1;
  S=0;


   for(j=1;j<=c&&ok;j++){
   q=s[j];
   nr=1;

     while(s[j]==q){

      if(!m[d][s[j]][nr]){
      ok=0;
      break;
      }

      S+=m[d][s[j]][nr];

     nr++;
     j++;
     }


   j--;
   }


    if(ok&&max<S)
    max=S;

  }
  }



return 0;
}



int main(){



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

fscanf(f,"%d %d",&N,&M);

s[0]=0;

  for(i=1;i<=N;i++){
  fscanf(f,"%d",&x);

    for(j=2;j<=20;j++){

     if(m[j][x%j][0]<5){
     m[j][x%j][0]++;
     m[j][x%j][m[j][x%j][0]]=x;

     p=m[j][x%j][0];

       for(l=p;l>1;l--){
	 if(m[j][x%j][l]>m[j][x%j][l-1]){
	 aux=m[j][x%j][l];
	 m[j][x%j][l]=m[j][x%j][l-1];
	 m[j][x%j][l-1]=aux;
	 }
       }


     }

     else{

     min=10000;

       for(l=1;l<=5;l++){
	 if(m[j][x%j][l]<min){
	 min=m[j][x%j][l];
	 p=j;
	 }

       }


     m[j][x%j][p]=x;

       for(l=p;l>1;l--){
	 if(m[j][x%j][l]>m[j][x%j][l-1]){
	 aux=m[j][x%j][l];
	 m[j][x%j][l]=m[j][x%j][l-1];
	 m[j][x%j][l-1]=aux;
	 }
       }

     }

    }


  }


  for(i=1;i<=M;i++){
  fscanf(f,"%d %d",&c,&d);


  max=-1;

  back(1);

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

  }




fclose(f);
fclose(g);
return 0;
}