#include <stdio.h>

int a[400000];

void sort(int n)
{
	int i,j,aux;

	for(i=0;i<n;i++)
		for(j=0;j<i;j++)
			if(a[j]<a[i]) { aux=a[j];a[j]=a[i];a[i]=aux;}
}

int min(int a, int b)
{
	return a>b?b:a;
}

int main(void)
{
	int i,j,n,k,teste,p,nr,sum=0,bestsum,i1,i2,i3,i4,i5,s2,s3,s4,s5,f2,f3,f4,f5,time;
	FILE *f=fopen("tricouri.in","r");
	FILE *fout=fopen("tricouri.out","w");
	
	fscanf(f,"%d %d",&n,&teste);
	for(i=0;i<n;i++) fscanf(f,"%d",&a[i]); a[n]=0;
	sort(n);
	for(k=0;k<teste;k++)
	{
		fscanf(f,"%d %d",&nr,&p);time=0;

		bestsum=-1;
		for(i1=0;i1<=5;i1++)
		{
			if(nr>1) { s2=i1+1;f2=min(10,n-1);} else { s2=n;f2=n;}
			for(i2=s2;i2<=f2;i2++)
			{
				if(nr>2) { s3=i2+1;f3=min(16,n-1);} else { s3=n;f3=n;}
				for(i3=s3;i3<=f3;i3++)
				{
					if(nr>3) { s4=i3+1;f4=min(24,n-1);} else { s4=n;f4=n;}
					for(i4=s4;i4<=f4;i4++)
					{
						if(nr>4) { s5=i4+1;f5=min(40,n-1);} else { s5=n;f5=n;}
						for(i5=s5;i5<=f5;i5++)
						{
							sum=a[i1]+a[i2]+a[i3]+a[i4]+a[i5];time++;
							if(sum%p==0&&sum>bestsum) bestsum=sum;
						}
					}
				}
			}
		}
		printf("%d\n",time);
		fprintf(fout,"%d\n",bestsum);
	}
	fclose(f);fclose(fout);

	return 0;
}