#include<stdio.h>
#include<set>

using namespace std;

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];
multiset<int>S[25];

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]];
	}
}

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 = 1 ; i <= n ; ++i ){
			int list = v[i]%p;
			S[list].insert(v[i]);
			if ( S[list].size() > 5 ){
				S[list].erase(S[list].begin());
			}
		}
		
		for ( i = 0 ; i < p ; ++i ){
			int k = 0;
			for ( set<int>::iterator itt = S[i].begin() ; itt != S[i].end() ; ++itt ){
				saved[i][++k] = (*itt);
			}
			saved[i][0] = k;
			S[i].clear();
		}
		
		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;
}