#include <bits/stdc++.h>
using namespace std;
ifstream in("tricouri.in");
ofstream out("tricouri.out");
const int inf=2e9+7;
vector<pair<int,int> > q[21];
vector<int> v,r[21];
int dp[6][21];
int ans[101];
int main()
{
    ios_base::sync_with_stdio(false);
    in.tie(0),out.tie(0);
    int n,t,x,k,p;
    in>>n>>t;
    for(int i=0;i<n;++i)
    {
        in>>x;
        v.push_back(x);
    }
    sort(v.begin(),v.end(),greater<int>());
    for(int i=0;i<t;++i)
    {
        in>>k>>p;
        q[p].push_back({k,i});
    }
    for(int p=2;p<=20;++p)
    if(!q[p].empty())
    {
        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:v)
        if(r[x%p].size()<5)
            r[x%p].push_back(x);
        for(int f=0;f<p;++f)
        for(int x:r[f])
        for(int e=4;e>=0;--e)
        for(int k=0;k<p;++k)
            dp[e+1][(k+f)%p]=max(dp[e+1][(k+f)%p],dp[e][k]+x);
        for(auto t:q[p])
            ans[t.second]=max(-1,dp[t.first][0]);
    }
    for(int i=0;i<t;++i)
        out<<ans[i]<<'\n';
    return 0;
}