#include <stdio.h>

long n, t[30000], m, k, p, s, smax;


void back (int j)
{
	int i;
	for (i=j; i<n; i++)
		{
			s += t[i];
			if (j==k-1)
				{if (s>smax && s%p==0) smax=s;}
			else
				back (j+1);
			s -= t[i];

		}
}

int main ()

{
	int i;
	FILE *f, *g;
	f=fopen ("tricouri.in", "r");
	g=fopen ("tricouri.out", "w");
	fscanf (f, "%ld %ld", &n, &m);
	for (i=0; i<n; i++)
		fscanf (f, "%ld ", &t[i]);
	for (i=0; i<m;  i++)
		{
			fscanf (f, "%ld %ld", &k, &p);
			smax=s=0;
			back (0);
			if (!smax) fprintf(g, "-1\n");
			else fprintf (g, "%ld\n", smax);
		}
	fclose(f);
	fclose(g);
	return 0;
}