#include<stdio.h>

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

int n,m,v[300000],k,p,c[6],s,smax=-1,i;

void sume(int x) {
   if(x==k) if(smax<s && s%p==0 && s>0) smax=s;
	    else ;
   else
      for(int j=c[x]+1;j<n-(k-x)+1;j++) {
	 c[x+1]=j;
	 s+=v[j];
	 sume(x+1);
	 s-=v[j];
      }

}

int main() {
   fscanf(f,"%d",&n); fscanf(f,"%d",&m);
   for(i=0;i<n;i++) fscanf(f,"%d",&v[i]);
   c[0]=-1;
   for(i=0;i<m;i++) {
      fscanf(f,"%d",&k); fscanf(f,"%d",&p);
      sume(0); fprintf(g,"%d\n",smax);
      s=0;
      smax=-1;
   }
   fclose(f);
   fclose(g);
   return 0;
}