#include <stdio.h>

int n,m,a[500000],k,p;
int r[21][20][6];
int took[21];
int bestsum,sum;

void precompute(void)
{
    int i,j,rest,poz;
    
    for(k=2;k<21;k++)
	for(i=0;i<20;i++)
	     for(j=0;j<6;j++) r[k][i][j]=-100000000;

    for(k=2;k<21;k++)	     
        for(i=0;i<n;i++)
	{
	    rest=a[i]%k;
	    poz=5;
	    while(a[i]>r[k][rest][poz] && poz>0) poz--;
	    if(poz<5)
	    {
		for(j=5;j>poz;j--) r[k][rest][j]=r[k][rest][j-1];
		r[k][rest][poz]=a[i];
	    }
	}
}

void print_test(int k)
{
    int i,j;

    printf("\n k= %d\n",k);
    for(i=0;i<k;i++)
    {
	for(j=0;j<5;j++)
	    printf("%d ",r[k][i][j]);
	printf("\n");
    }
    printf("\n\n");
}

// -1 inseamna imposibilitate, nu trebuie selectat
int main(void)
{
    FILE *f=fopen("tricouri.in","r");
    FILE *fout=fopen("tricouri.out","w");
    int i,j,i1,i2,i3,i4,i0,j0,i5;

    fscanf(f,"%d %d",&n,&m);
    for(i=0;i<n;i++) fscanf(f,"%d",&a[i]);
    
    precompute();
    
    
    for(i=0;i<m;i++)
    {
	fscanf(f,"%d %d",&p,&k);
	bestsum=-1;
	if(p==1)
	{
	    i1=0;
	    sum=r[k][i1][0];
	    if(sum>bestsum) bestsum=sum;
	}
	
	if(p==2)
	{
	    for(i1=0;i1<k;i1++)
	    {
		i2=(k-i1)%k;
		for(i0=0;i0<k;i0++) took[i0]=0;
		took[i1]++;took[i2]++;
		sum=0;
		for(i0=0;i0<k;i0++)
		    for(j0=0;j0<took[i0];j0++) sum+=r[k][i0][j0];
		if(sum>bestsum) bestsum=sum;
	    }
	}
	
	if(p==3)
	{
	    for(i1=0;i1<k;i1++)
		for(i2=i1;i2<k;i2++)
		{
		    i3=(2*k-i1-i2)%k;
		    for(i0=0;i0<k;i0++) took[i0]=0;
		    took[i1]++;took[i2]++;took[i3]++;
		    sum=0;
    		    for(i0=0;i0<k;i0++)
		    for(j0=0;j0<took[i0];j0++) sum+=r[k][i0][j0];
		    if(sum>bestsum) bestsum=sum;		    
		}
	
	}
	
	if(p==4)
	{
	    for(i1=0;i1<k;i1++)
		for(i2=i1;i2<k;i2++)
		    for(i3=i2;i3<k;i3++)
		    {
		        i4=(3*k-i1-i2-i3)%k;
			for(i0=0;i0<k;i0++) took[i0]=0;
			took[i1]++;took[i2]++;took[i3]++;took[i4]++;
			sum=0;
			for(i0=0;i0<k;i0++)
			for(j0=0;j0<took[i0];j0++) sum+=r[k][i0][j0];
			if(sum>bestsum) bestsum=sum;			
		    }
	}
	
	if(p==5)
	{
	    for(i1=0;i1<k;i1++)
		for(i2=i1;i2<k;i2++)
		    for(i3=i2;i3<k;i3++)
			for(i4=i3;i4<k;i4++)
			{
    		    	    i5=(4*k-i1-i2-i3-i4)%k;
			    for(i0=0;i0<k;i0++) took[i0]=0;
			    took[i1]++;took[i2]++;took[i3]++;took[i4]++;took[i5]++;
		            sum=0;
			    for(i0=0;i0<k;i0++)
			    for(j0=0;j0<took[i0];j0++) sum+=r[k][i0][j0];
			    if(sum>bestsum) bestsum=sum;
			}	
	}
	
	print_test(k);
	fprintf(fout,"%d\n",bestsum);
    }

    fclose(f);fclose(fout);    
    return 0;
}