#include <cstdio>
#include <algorithm>
#include <vector>
#define NMAX 7
#define MMAX 27
using namespace std;
vector <int> H[NMAX][MMAX],v;
int D[NMAX][MMAX];
int n, Q, X[300007];
inline int Cmp(int a, int b){return a > b;}
int main()
{   freopen("tricouri.in", "r", stdin);
    freopen("tricouri.out", "w", stdout);
    scanf("%d %d",&n,&Q);
    for(int i=1;i<=n;++i) scanf("%d",&X[i]);
    sort(X+1,X+n+1,Cmp);
    for(int i=1;i<=n;++i)
        for(int j=2;j<=20;++j)
            if(H[j][X[i]%j].size()<5) H[j][X[i]%j].push_back(X[i]);
    for(;Q;--Q)
	{   int k=0,p=0;
        scanf("%d %d",&k,&p);
        for(int i=0;i<=k;++i)
            for(int j=0;j<=p;++j) D[i][j]=0;
        v.clear();
        for(int i=0;i<=p;++i)
		{	vector <int>::iterator it=H[p][i].begin(), sf=H[p][i].end();
			for(;it!=sf;++it) v.push_back(*it);
		}
        for(unsigned int i=0;i<v.size();++i)
		{   for(int j=k-1;j>=0;--j)
                for(int l=0;l<p;++l)
                    if(D[j][l]!=0) D[j+1][(l+v[i])%p]=max(D[j][l]+v[i],D[j+1][(l+v[i])%p]);
            if(D[1][v[i]%p]==0) D[1][v[i]%p]=v[i];
        }
        if(D[k][0]==0) D[k][0]=-1;
        printf("%d\n",D[k][0]);
    }
    return 0;
}