#include <stdio.h>

void com_pl(int);
int final(int);
int valid(int);
void scrie();

int n,c=0,tric[100000],m,k,p2,max,pick[100000][2],sum;
int main()
{
 FILE *in=fopen("tricouri.in","rt"),*out=fopen("tricouri.out","w+");
 int i,j;
 fclose(out);
 fscanf(in,"%d%d",&n,&m);
 for(i=0;i<n;i++)
  fscanf(in,"%d",&tric[i]);

 for(i=0;i<m;i++){
  max=0;
  fscanf(in,"%d%d",&k,&p2);
  for(j=0;j<k;j++)
   pick[j][1]=-1;
  com_pl(0);
 FILE *out=fopen("tricouri.out","a");
 if(max)
  fprintf(out,"%d\n",max);
 else
  fprintf(out,"-1\n");
 fclose(out);
return 1;
 }


 fclose(in);
return 1;
}

void fmax(){
 if(sum>max)
  max=sum;
}

void com_pl(int p)
{
 int v;
 for(v=0;v<n;v++)
    {
     c=0;
     for(int i=0;i<k;i++)
      if(v==pick[i][1])
       c=1;
     if(c)continue;
     pick[p][0]=tric[v];
     pick[p][1]=v;
      if(valid(p))
       if(final(p)) fmax();
       else com_pl(p+1);
    }
}

int final(int p)
{
 return p==k-1;
}


int valid(int p)
{
 if(p!=k-1)return 1;
 int i;sum=0;
 for(i=0;i<k;i++)
  sum+=pick[i][0];

 if(sum%p2==0)
  return 1;
 else
  return 0;
}