#include <bits/stdc++.h>
using namespace std;
ifstream in("tricouri.in");
ofstream out("tricouri.out");
const int lim=1e6+3;
const int inf=2e9+7;
int f[lim];
vector<int> nr;
vector<int> r[23];
struct query
{
    int k;
    int ind;
};
vector<query> v[23];
int ans[105];
int lmax[23];
int dp[7][23];
void create_r(int p)
{
    for(int i=0;i<p;++i)
    {
        for(int j=0;j<=5;++j)
            dp[j][i]=-inf;
        r[i].clear();
    }
    dp[0][0]=0;
    for(int x:nr) if(r[x%p].size()<lmax[p])
        r[x%p].push_back(x);
}
int main()
{
    int n,q,x,k,p,maxim=0;
    in>>n>>q;
    for(int i=1;i<=n;++i)
    {
        in>>x;
        f[x]++;
        maxim=max(maxim,x);
    }
    for(int i=maxim;i>=1;--i) if(f[i]>0)
    for(int j=1;j<=f[i];++j)
        nr.push_back(i);
    for(int i=1;i<=q;++i)
    {
        in>>k>>p;
        v[p].push_back({k,i});
        lmax[p]=max(lmax[p],k);
    }
    for(int p=2;p<=20;++p)
    if(!v[p].empty())
    {
        create_r(p);
        for(int kr=0;kr<p;++kr)
        for(int i=0;i<r[kr].size();++i)
        for(int e=lmax[p]-1;e>=0;--e)
        for(int tr=0;tr<p;++tr)
            dp[e+1][(tr+kr)%p]=max(dp[e+1][(tr+kr)%p],dp[e][tr]+r[kr][i]);
        for(auto t:v[p])
        if(dp[t.k][0]<0)
            ans[t.ind]=-1;
        else ans[t.ind]=dp[t.k][0];
    }
    for(int i=1;i<=q;++i)
        out<<ans[i]<<'\n';
    return 0;
}