#include<stdio.h>

FILE*f=fopen("tricouri.in","r");
FILE*g=fopen("tricouri.out","w");

int n,q,sum,i,k,p,x[30];
int D[7][25],saved[25][7],next[25],v[300005];

inline int max ( const int &a , const int &b ){
	return a >= b ? a : b;
}

void back ( int niv ){
	
	if ( niv == k ){
		int nec = p - (sum % p); if ( nec == p )	nec = 0;
		if ( next[nec] == 0 )	return ;
		sum += saved[nec][next[nec]];
		D[k][p] = max(D[k][p],sum);
		sum -= saved[nec][next[nec]];
		return ;
	}
	
	for ( int i = 0 ; i < p ; ++i ){
		if ( next[i] <= 0 )	continue ;
		sum += saved[i][next[i]--];
		back(niv+1);
		sum -= saved[i][++next[i]];
	}
}

inline void trage ( int poz , int list ){
	
	for ( int i = 1 ; i < poz ; ++i ){
		saved[list][i] = saved[list][i+1];
	}
}

inline void push ( int poz , int list ){
	
	for ( int i = saved[list][0] + 1 ; i > poz ; --i ){
		saved[list][i] = saved[list][i-1];
	}
}

inline void adauga ( int val , int list ){
	
	if ( saved[list][0] == 5 ){
		for ( int i = 5 ; i >= 1 ; --i ){
			if ( saved[list][i] < val ){
				trage(i,list);
				saved[list][i] = val;
				break ;
			}
		}
	}
	else{
		int i;
		for ( i = saved[list][0] ; i >= 1 ; --i ){
			if ( saved[list][i] < val ){
				push(i+1,list);
				saved[list][i+1] = val;
				break ;
			}
		}
		++saved[list][0];
		if ( i == 0 ){
			push(1,list);
			saved[list][1] = val;
		}
	}
}

int main () {
	
	fscanf(f,"%d %d",&n,&q);
	
	for ( i = 1 ; i <= n ; ++i ){
		fscanf(f,"%d",&v[i]);
	}
	
	for ( p = 2 ; p <= 20 ; ++p ){
		
		for ( i = 0 ; i < p ; ++i ){
			saved[i][0] = 0;
		}
		
		for ( i = 1 ; i <= n ; ++i ){
			int list = v[i]%p;
			adauga(v[i],list);
		}
		
		for ( k = 1 ; k <= 5 ; ++k ){
			D[k][p] = -1;
			for ( int u = 0 ; u < p ; ++u ){
				next[u] = saved[u][0];
			}
			back(1);
		}
	}
	
	for ( i = 1 ; i <= q ; ++i ){
		fscanf(f,"%d %d",&k,&p);
		fprintf(g,"%d\n",D[k][p]);
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}