#include <stdio.h>

#define nm 300000
#define km 8
#define pm 16

int n, m, p, c[km][pm], sol[km][pm], a[nm];

int main()
{
	int i, j, k;

	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 (p = 2; p <= 20; ++p)
    {
    	for (j = 0; j <= 5; ++j)
        	for (k = 0; k < p; ++k)
            	c[j][k] = -1;
    
        c[0][0] = 0;

        for (i = 0; i < n; ++i)
    		for (j = 4; j >= 0; --j)
        		for (k = p - 1; k >= 0; --k)
                	if (c[j][k] != -1 && c[j + 1][(k + a[i + 1]) % p] < c[j][k] + a[i + 1])
                    	c[j + 1][(k + a[i + 1]) % p] = c[j][k] + a[i + 1];

    	for (j = 1; j <= 5; ++j)
        	if (c[j][0])
		   		sol[p][j] = c[j][0];
            else
            	sol[p][j] = -1;
    }

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

        printf("%d\n", sol[p][k]);
    }

	return 0;
}