#include <stdio.h>
#include <memory.h>

#define NMAX 300010
#define INFI 0x3f3f3f3f

long long max[5][NMAX][21];
int a[NMAX];
int n, m;

inline long long MAX(long long a, long long b)
{
	return (a > b) ? (a) : (b);
}

void read()
{
	int i;
	scanf("%d%d", &n, &m);
	for(i = 1; i <= n; ++i)
		scanf("%d", a+i);
}

long long dinamic(int k, int p)
{
	int i, j, r;

	memset(max, -INFI, sizeof(max));

	for(j = 1; j <= n; ++j)
		max[1][j][ a[j]%p ] = MAX(max[1][j][ a[j]%p ], a[j]);

	for(i = 2; i <= k; ++i)
		for(j = i; j <= n; ++j)
			for(r = 0; r < p; ++r)
				max[i][j][ (r + a[j]%p)%p ] = MAX(max[i][j-1][ (r + a[j]%p)%p ], max[i-1][j-1][ r ] + a[j]);
    if(max[k][n][0] < 0)
                    return -1;

	return max[k][n][0];
}

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

	read();

	for(int i = 1, k, p; i <= m; ++i)
	{
		scanf("%d%d", &k, &p);
		printf("%lld\n", dinamic(k, p));
	}

	return 0;
}