#include <cstdio>
#include <cstring>

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[2][MAX_K][MAX_P];

template <class T> T max(T a, T b) { return (a > b) ? a : b; }

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)
		{
			memset(d[q ^ 1], 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[q ^ 1][j][r] = max(d[q ^ 1][j][r], d[q][j][r]);
						d[q ^ 1][j + 1][(r + a[i]) % p] = max(d[q ^ 1][j + 1][(r + a[i + 1]) % p], d[q][j][r] + a[i + 1]);
					}
		}

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