#include <stdio.h>

#define maxl 6
#define mod 21

int n,m;
int 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,x,j,k,p;
    
	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<=n;i++)
	{
		scanf("%d",&x);

		for (j=0;j<maxl;j++)
		  for (k=2;k<mod;k++)
			for (p=0;p<mod;p++) d[j][k][p]=c[j][k][p];

		for (j=0;j<maxl-1;j++)
		  for (k=2;k<mod;k++)
            for (p=0;p<mod;p++)
              if ((d[j][k][p]!=-1) && (d[j][k][p]+x>c[j+1][k][(p+x)%k])) c[j+1][k][(p+x)%k]=d[j][k][p]+x;
	}
    
    for (i=1;i<=m;i++)
    {
        scanf("%d %d",&j,&k);
        printf("%d\n",c[j][k][0]);
    }
    
    return 0;
}