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

const int MAX_N = 300010;
const int MAX_K = 8;
const int MAX_P = 22;

int n, m, k, p;
int a[MAX_N];
int d[MAX_N][MAX_K][MAX_P];

int cmp(int a, int b)
{
	return a % p < b % p;
}

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

	scanf("%d %d", &n, &m);

	for (i = 1; i <= n; ++i)
		scanf("%d", &a[i]);

	for (t = 1; t <= m; ++t)
	{
		scanf("%d %d", &k, &p);

		for (i = 1; i <= n; ++i)
		{
			d[i][1][a[i] % p] = max(d[i][1][a[i % p]], a[i]);

			for (j = 1; j <= i && j <= k; ++j)
				for (r = 0; r < p; ++r)
					if (d[i][j][r])
					{
						d[i + 1][j][r] = max(d[i + 1][j][r], d[i][j][r]);
						d[i + 1][j + 1][(r + a[i + 1]) % p] = max(d[i + 1][j + 1][(r + a[i + 1]) % p], d[i][j][r] + a[i + 1]);
					}
			memset(d[i - 1], 0, sizeof(d[i]));
		}

		printf("%d\n", (d[n][k][0]) ? d[n][k][0] : -1);
		memset(d[n], 0, sizeof(d[n]));
	}
}