#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define nmax 300010
#define oo 1000000000

int i,j,l,n,m,a[nmax],best[2][10][25],bn,k,p;

int main()
{
	freopen("tricouri.in","r",stdin);
	freopen("tricouri.out","w",stdout);

	scanf("%d%d",&n,&m);
	for (i=0;i<n;i++)
		scanf("%d",a+i);
	for (;m;--m)
	{
		scanf("%d%d",&k,&p);
		for (i=0;i<6;i++)
			for (j=0;j<21;j++)
				best[bn][i][j]=-oo;
		best[bn][0][0]=0;
		for (i=0;i<n;i++)
		{
			memcpy(best[1-bn],best[bn],sizeof(best[0]));
			for (j=0;j<k;j++)
				for (l=0;l<p;l++)
					if (best[1-bn][j+1][(l+a[i])%p]<best[bn][j][l]+a[i])
						best[1-bn][j+1][(l+a[i])%p]=best[bn][j][l]+a[i];
			bn=1-bn;
		}
		printf("%d\n",(best[bn][k][0]>=0?best[bn][k][0]:-1));
	}

	return 0;
}