/*
Dupa ce citim cele N numere din fisierul de intrare, vom realiza o preprocesare (filtrare) in urmatorul mod: 
M[i,j] va fi o lista ( implementata fie ca vector, fie ca lista liniara simplu inlantuita ) care va retine in ordine descrescatoare
numerele din fisierul de intrare care dau restul j la impartirea cu i. Deoarece pentru fiecare interogare numarul de termeni este 
cel mult 5, este suficient ca aceasta lista sa retina cel mult 5 termeni. Astfel, in momentul in care citim un element de valoare x, 
pentru fiecare i de la 2 la 20, vom introduce elementul in lista Mi, x mod i daca si numai daca aceasta lista nu contine inca 5 termeni 
sau x este mai mare decat minimul din lista ( in acest ultim caz x va fi copiat peste acest minim, asigurand ca in lista vor ramane 
cele mai mari numere posibile ).
In momentul in care citim o interogare de forma K P, vom genera toate posibilitatile de resturi la impartirea cu P ale primelor K-1 
numere din suma, al K-lea rest fiind unic determinat. Pentru o astfel de configuratie de resturi stim in timp O(1) care este cea mai mare suma ( daca exista ) a unor elemente care sa aiba resturile astfel stabilite, prin utilizarea informatiilor din tabloul M. 
De exemplu, daca K = 3 si P = 4, pentru primele doua resturi stabilite ale primelor doua numere 
( sa zicem ca aceste resturi au valoarea 3 si respectiv 2), restul celui de-al treilea numar la impartirea cu 4 nu poate fi decat 3. 
Acum, folosind tabloul M calculat anterior, trebuie sa stim care sunt cele mai mari doua numere care dau la impartirea cu 4 restul 3 si 
care este cel mai mare numar care la impartirea cu 4 da restul 2. Aceasta suma poate fi calculata deci in O(1). 
Vom genera ( prin metoda backtracking sau folosind mai multe for-uri imbricate ) toate configuratiile posibile de resturi, 
si o vom retine pe cea care genereaza suma cea mai mare, suma pe care ulterior o vom afisa. Complexitatea finala este deci O(N + M * PK-1),
care asigura punctajul maxim, folosind nivelul cunostintelor de clasa a IX-a.

O alta solutie mai eleganta dar care depaseste cunostintele de clasa a IX-a ar fi cea care foloseste programarea dinamica 
in modul urmator: se noteaza cu Di,j,r care este suma maxima folosind i numere din primele j resturi posibile la impartirea cu P 
si pana in momentul curent sa avem format restul r. Se construieste acest tablou in mod bottom-up. Raspunsul se va afla in DK,P-1,0.
 Complexitatea unui astfel de algoritm este O(N + M * K2 * P2), care de asemenea obtine 100 de puncte.
*/
#include<cstdio>   
#include<algorithm>   
#define INF 1000010
#define LG 700000
using namespace std;     
int viz[21],rez,nr[21],j,i,l,r,a[21][21][6],minn,k,s[6],p,S,v[300010],P,maxx,n,m,ind;
char buffer[LG];
inline void Citeste(int &x)
{   while(buffer[ind]<'0' || '9'<buffer[ind])
    {   ind++;
        if(ind==LG) {fread(buffer,1,LG,stdin); ind=0;}
    }
    x=0;
    while('0'<=buffer[ind] && buffer[ind]<='9')
    {   x=x*10+buffer[ind]-'0';
        ind++;
        if(ind==LG) {fread(buffer,1,LG,stdin); ind=0;}
    }
}
//int cmp(int a,int b){return a>b;} 
struct cmp
{   bool operator()(const int &a, const int &b) const
    {   
        return (a>b);
    }
};

void back(int x)
{   int i;   
	if(x<=k-1)
	{	for(i=s[x-1];i<P;i++)
		{	if(nr[i]<a[P][i][0])
			{	s[x]=i; nr[s[x]]++;   
				S+=a[P][i][ nr[s[x]]];
				back(x+1);   
				S-=a[P][i][ nr[s[x]] ] ;
				nr[s[x]]--;   
			}   
		}   
	}   
	else
	{	rez=S%P; rez=P-rez;
		if(rez==P) rez=0;
		if(nr[rez]<a[P][rez][0])
			if(S+a[P][rez][ nr[rez]+1 ]>maxx) maxx=S+a[P][rez][ nr[rez]+1];
	}   
}   
int main()
{   freopen("tricouri.in","r",stdin);
    freopen("tricouri.out","w",stdout); 
	Citeste(n); Citeste(m);//scanf("%d %d",&n,&m);   
	for(i=1;i<=n;i++) Citeste(v[i]); //scanf("%d",&v[i]);      
	for(l=1;l<=m;l++)
	{   Citeste(k); Citeste(P);//scanf("%d %d",&k,&P);   
		if(!viz[P])
		{	for(i=1;i<=n;i++)
			{   r=v[i]%P;   
				if(a[P][r][0]<5) {a[P][r][0]++; a[P][r][a[P][r][0]]=v[i];}   
				else
				{	minn=INF;   
					for(j=1;j<=5;j++)
					   if(a[P][r][j]<minn) {minn=a[P][r][j]; p=j;}   
					if(minn<v[i]) a[P][r][p]=v[i];
				}   
			}   
		}
		for(i=0;i<P;i++) sort(a[P][i]+1,a[P][i]+a[P][i][0]+1,cmp());
		maxx=-1; S=0;   
		back(1);   
		printf("%d\n",maxx);   
        viz[P]=1;
		for(i=0;i<=P;i++) nr[i]=0;
	}    
	return 0;   
}