#include <cstdio>
#include <string.h>
#include <algorithm>

using namespace std;

#define Pmax 21

int n, m;
int A[Pmax][Pmax][6];
int rez[Pmax][6][Pmax];

void readdata()
{
	freopen("tricouri.in", "r", stdin);
	freopen("tricouri.out", "w", stdout);
	
	int i, j, k, l, poz, best, val;
	
	scanf("%d %d", &n, &m);
	for (i = 0; i < n; ++i)
	{
		scanf("%d", &val);
		for (j = 2; j <= 20; ++j)
		{
			k = val % j;
			best = val;
			poz = 6;
			for (l = 1; l < 6; ++l)
				if (A[j][k][l] < best)
				{
					best = A[j][k][l];
					poz = l;
				}
			if (poz < 6) A[j][k][poz] = val;
		}
	}
}

void preprocesare()
{
	int i, j, k, l, p, val;
	
	for (i = 2; i <= 20; ++i)
	{
		for (j = 0; j < i; ++j) for (k = 1; k < 6; ++k)
		{
			val = A[i][j][k];
			for (l = 4; l >= 0; --l)
				for (p = 0; p < i; ++p)
				if (l > 0 || p == 0)
					rez[i][l+1][(p+j)%i] = max(rez[i][l+1][(p+j)%i], (rez[i][l][p]+val));
		}
	}
}

void solve()
{
	int k, p;
	
	for (; m; --m)
	{
		scanf("%d %d", &k, &p);
		printf("%d\n", rez[p][k][0] == 0 ? -1 : rez[p][k][0]);
	}
}

int main()
{
	readdata();
	preprocesare();
	solve();
	return 0;
}