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

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<=5;i++)
  for(j=2;j<=20;j++)
   ba[i][j]=back(i,j);
 for(i=1;i<=m;i++)
 {scanf("%d%d",&k,&p);
  printf("%lld\n",ba[i][j]);
  }
 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;
 if(n==1)
   if(max[p][0][1])
	 return max[p][0][1];
   else
	return -1;
 while(k>0)
  {st[k]++;
   if(st[k]<=p)
	if(k==n-1)
	   {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;break;}
		   suma+=st[i]-1;
		   }

		 if(!max[p][(p-suma%p)%p][++nr[(p-suma%p)%p+1]])
			bun=0;
		 else
		   sol+=max[p][(p-suma%p)%p][nr[(p-suma%p)%p+1]];
		 if(sol>maxim&&bun)
		   maxim=sol;
		}
	 else
	   k++;


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