#include <cstdio>
#include <algorithm>
using namespace std;

int v[300005];

int main()
{
	int nr,d,n,m,i,j;
	freopen("tricouri.in","r",stdin);
	freopen("tricouri.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (i=1;i<=n;++i) scanf("%d",&v[i]);
	sort(v+1,v+n+1);
	for (i=1;i<=m;++i)
	{
		scanf("%d %d",&nr,&d);
		int nr2,rest,completed=0,ok[25],go=0,x[105],sol[7][23];
		
		for (j=0;j<=d;++j) ok[j]=0;
		
		for (j=n;(j>0) && (completed<nr);--j)
			if (ok[v[j]%d]<nr) ++ok[v[j]%d],++go,x[go]=v[j];
		
		for (j=1;j<=nr;++j)
			for (rest=0;rest<d;++rest)
				sol[j][rest]=-1;
		
		
		for (j=1;j<=go;++j)
			{
				for (nr2=nr-1;nr2>0;--nr2)
					for (rest=0;rest<d;++rest)
						if ((sol[nr2][rest]>0) && (sol[nr2+1][(rest+x[j]%d)%d]<sol[nr2][rest]+x[j]))
							sol[nr2+1][(rest+x[j]%d)%d]=sol[nr2][rest]+x[j];
				if (sol[1][x[j]%d]<x[j]) sol[1][x[j]%d]=x[j];
		    }				
		printf("%d\n",sol[nr][0]);
	}
	return 0;}