#include <fstream.h>
#include <string.h>
ifstream f("tricouri.in");
ofstream g("tricouri.out");
int n,t,i,j,k1,m[21][6][21],k,p,y,w,x,nr,v[2001],a[2001][20],b[2001][20];
int main(){
f>>n>>t;
for(i=1;i<=n;i++)
  { f>>x;
    for(j=2;j<=20;j++)
      for(k=1;k<=5;k++)
	if(m[x%j][k][j]<x)
	    { for(y=5;y>=k;y--)
		 if(m[x%j][y][j]!=0)
		     m[x%j][y+1][j]=m[x%j][y][j];

	      m[x%j][k][j]=x;
	     k=6;
	    }

    }
for(i=1;i<=t;i++){
  f>>k1>>p;   nr=0;
  for(j=0;j<20;j++)
    for(x=1;x<=k1;x++)
      if(m[j][x][p]!=0)
       {nr++;	v[nr]=m[j][x][p];}

   for(j=1;j<=nr;j++)
   {  for(k=0;k<=j;k++)
	a[j][k]=a[j-1][k];
	 a[j][v[j]%p]=a[j-1][v[j]%p];
    if(a[j][v[j]%p]<v[j])
      a[j][v[j]%p]=v[j];
    }
   for(j=2;j<=k1;j++) {
     for(x=j;x<=nr;x++)
      for(k=0;k<=p-1;k++){
       if(b[x][k]<b[x-1][k])
	b[x][k]=b[x-1][k];
      if(a[x-1][k]+v[x]>b[x][(v[x]+k)%p]&&a[x-1][k]!=0)
	 b[x][(v[x]+k)%p]=a[x-1][k]+v[x];
       }
    memcpy(a,b,sizeof(int)*2001*20);
    memset(b,0,sizeof(int)*2001*20);
     }
    if(a[nr][0]==0)
     g<<-1<<'\n';
    else
    g<<a[nr][0]<<'\n';
     }
return 0;
}