#include<stdio.h>
#include<fstream.h>
#define kmax 7
#define pmax 23
#define nmax 300000
#define infi 1000002
int long max[pmax][pmax][kmax];
int long back(int ,int);

int main()
{int i,j,k,p,d;
 int long a[nmax],n,m,b;
 freopen("tricouri.in","r",stdin);
 freopen("tricouri.out","w",stdout);

 scanf("%ld%ld",&n,&m);
 for(i=1;i<=n;i++)
  {scanf("%ld",&a[i]);
   //a[i]--;
   for(j=1;j<=pmax-2;j++)
	 {b=a[i]%j;
	  d=5;
	  max[j][b][0]=infi;
	  while(max[j][b][d]<a[i]&&d>=0)
	   {max[j][b][d+1]=max[j][b][d];
		max[j][b][d--]=a[i];
		}
	  }


  }
 for(i=1;i<=m;i++)
 {scanf("%d%d",&k,&p);
  printf("%lld\n",back(k,p));
  }
 fclose(stdout);
 return 0;


}

long long back(int n,int p)
{int k=1,i,nr[pmax],st[kmax],bun,suma;
 long long maxim=-1;
 long long sol;
 memset(st,0,sizeof(st));
 st[1]=0;
 while(k>0)
  {st[k]++;
   if(st[k]<=p)
	if(k==n)
	   {memset(nr,0,sizeof(nr));
		for(i=1,bun=1,suma=0,sol=0;i<=n;i++)
		  {sol+=max[p][st[i]-1][++nr[st[i]]];
		   if(!max[p][st[i]-1][nr[st[i]]])
			 bun=0;
		   suma+=st[i]-1;
		   }
		 if(!(suma%p)&&sol>maxim&&bun)
		   maxim=sol;
		}
	 else
	   k++;


   else
	st[k--]=0;
   }
 return maxim;
  }