# include <stdio.h>

# define  _fin  "tricouri.in"
# define  _fout "tricouri.out"

# define  maxp  22
# define  maxk  7

typedef struct slist
{
	int a[maxk], l, poz;
}	slist;

void insert(slist &l, int el)
{
	int i, j;
	if ( !l.l ? el > l.a[l.l-1] : 1 )
	{
		for (i=0; i<l.l && el < l.a[i]; i++);
		for (j=l.l; j>i; j--) l.a[j] = l.a[j-1];
		
		l.a[i] = el;
		if ( ++l.l > 5 ) l.l = 5;
	}
}

inline void init(slist &l) { l.poz = 0; }
inline int  get (slist &l) { return l.poz+1<=l.l ? l.a[ l.poz++ ] : -1000; }

slist a[maxp][maxp];
int n, m;

void readf()
{
	freopen(_fin, "r", stdin);
	int i, x, j;
	
	for (scanf("%d %d", &n, &m), i=1; i<=n; i++)
		for (scanf("%d", &x), j=2; j<=20; j++)
			insert(a[j][x%j], x);
}

void reinitall()
{
	int i, j;
	for (i=0; i<20; i++) for (j=0; j<20; j++) a[i][j].poz = 0;
}

void solve()
{
	freopen(_fout, "w", stdout);
	
	int i, k, p, r1, r2, r3, r4, e1, e2, e3, e4, e5, smax, aux;
	
	for (i=1; i<=m; i++)
	{
		scanf("%d %d", &k, &p);
		
		// aflam suma maxima
		smax=0;
		reinitall();
		
		for (r1=0; r1<(k>1?p:1); r1++)
			for (r2=0; r2<(k>2?p:1); r2++)
				for (r3=0; r3<(k>3?p:1); r3++)
					for (r4=0; r4<(k>4?p:1); r4++)
					{
						e1 = k>1 ? r1 : 0;
						e2 = k>2 ? r2 : ( p - (r1) % p ) % p;
						e3 = k>3 ? r3 : ( p - (r1+r2) % p ) % p;
						e4 = k>4 ? r4 : ( p - (r1+r2+r3) % p ) % p;
						e5 = ( p - (r1+r2+r3+r4) % p ) % p;
						
						aux = 	get(a[p][e1]) +
								( k>1 ? get(a[p][e2]) : 0 ) +
								( k>2 ? get(a[p][e3]) : 0 ) +
								( k>3 ? get(a[p][e4]) : 0 ) +
								( k>4 ? get(a[p][e5]) : 0 );
						
						if ( aux > smax ) smax = aux;
						
						a[p][e1].poz = a[p][e2].poz = a[p][e3].poz = a[p][e4].poz = a[p][e5].poz = 0;
					}
		
		printf("%d\n", smax?smax:-1);
	}
}

int main()
{
	readf();
	solve();
	
	return 0;
}