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

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

int n, m, k, p, q;
int a[MAX_N];
int d[1000][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)
	{
		memset(d, 0, sizeof(d));
		scanf("%d %d", &k, &p);

		for (i = 1, q = 1; i <= n; ++i, q = 1 - q)
		{
			memset(d[1 - q], 0, sizeof(d[1 - q]));
			d[q][1][a[i] % p] = max(d[q][1][a[i % p]], a[i]);

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

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