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

int v[25][25][10], s[7][110], n, m, k, p;

int main()
{
    freopen("tricouri.in","r",stdin);
	freopen("tricouri.out","w",stdout);
	scanf("%d %d",&n,&m);
	int i, x, j, y;
	for (i=1; i<=n; i++)
	{
	    scanf("%d",&x);
		for (j=2; j<=20; j++)
        {
			k=x%j;
			p=0;
			for (y=1; y<=v[j][k][0]; y++)
			    if (v[j][k][y]>=x)
				{
				    p=y;
					break;
                }
			p++;
        	for (y=5; y>=p; y--) v[j][k][y+1]=v[j][k][y];
			v[j][k][p]=x;
			if (v[j][k][0]<5) v[j][k][0]++;
        }
    }
	int c, r;
	while (m--)
	{
		scanf("%d %d",&k,&p);
		n=k*(p-1);
		for (y=0; y<p; y++)
		    for (c=1; c<=min(k,v[p][y][0]); c++)
        		for (i=k; i>0; i--)
	        	    for (j=n-y; j>=0; j--)
		        		if (s[i-1][j] || (i==1 && j==0))
						    s[i][j+y]=max(s[i][j+y],s[i-1][j]+v[p][y][c]);
		r=-1;
		for (i=0; i<=n; i++)
		    if (!(i %p) && s[k][i]) r=max(r,s[k][i]);
        printf("%d\n",r);
		for (i=1; i<=k; i++)
		    for (j=0; j<=n; j++) s[i][j]=0;
    }
}