#include <stdio.h>

#define maxl 6
#define mod 21

int n,m;
int a[maxl][mod][mod],c[maxl][mod][mod],d[maxl][mod][mod];

int main()
{
    freopen("tricouri.in","r",stdin);
    freopen("tricouri.out","w",stdout);
    
    scanf("%d %d",&n,&m);
    
    int i,j,k,x,y,z;
    
    for (i=1;i<=n;i++)
    {
        scanf("%d",&x);
        for (j=2;j<mod;j++)
          for (k=1;k<maxl;k++)
            if (x>a[k][j][x%j]) a[k][j][x%j]=x;
    }
    
    for (i=0;i<maxl;i++)
      for (j=2;j<mod;j++)
        for (k=0;k<mod;k++) c[i][j][k]=-1;
        
    for (i=0;i<mod;i++) c[0][i][0]=0;
    
    for (i=1;i<maxl;i++)
      for (j=2;j<mod;j++)
		for (k=1;k<j;k++)
		  if (a[i][j][k]!=0)
		  {
			for (x=0;x<maxl;x++)
			  for (y=0;y<j;y++) d[x][j][y]=c[x][j][y];

			for (x=0;x<maxl;x++)
			  for (y=0;y<j;y++)
				if ((d[x][j][y]!=-1) && (d[x][j][y]+a[i][j][k]>c[x+1][j][(y+a[i][j][k])%j]))
				  c[x+1][j][(y+a[i][j][k])%j]=d[x][j][y]+a[i][j][k];

		  }

	for (i=1;i<=m;i++)
	{
        scanf("%d %d",&x,&y);
        printf("%d\n",c[x][y][0]);
    }         
    
    return 0;       
    
}