#include <stdio.h>

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

int n,c=0,tric[1000],m,k,p2,max,pick[1000],sum;

void main()
{
 FILE *in=fopen("tricouri.in","rt"),*out=fopen("tricouri.out","w+");
 int i;
 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);
  compl(0);
 FILE *out=fopen("tricouri.out","a");
 if(max)
  fprintf(out,"%d\n",max);
 else
  fprintf(out,"-1\n");
 fclose(out);

 }


 fclose(in);
}

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

void compl(int p)
{
 int v;
 for(v=0;v<n;v++)
    {
     pick[p]=tric[v];
     if(valid(p))
       if(final(p)) fmax();
       else compl(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];

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