#include<fstream>
#include<algorithm>

using namespace std;

const char iname[]="tricouri.in";
const char oname[]="tricouri.out";
const int maxn=300005;
const int maxk=6;
const int maxp=22;

ifstream f(iname);
ofstream g(oname);

int a[maxp][maxp][maxk],l[maxn],dp[maxk][maxp],i,j,n,k,p,m,r;

inline void add(int *a,int x)
{
    a[0]=x;
    int i,aux;
    for(i=0;i<5&&a[i]>a[i+1];++i)
        aux=a[i],a[i]=a[i+1],a[i+1]=aux;
}

int main()
{
    f>>n>>m;
    for(i=1;i<=n;++i)
    {
        f>>k;
        for(j=2;j<=20;++j)
            add(a[j][k%j],k);
    }
    while(m--)
    {
        f>>k>>p;
        l[0]=0;
        for(i=0;i<p;++i)
            for(j=1;j<=5;++j)
                if(a[p][i][j])
                    l[++l[0]]=a[p][i][j];
        memset(dp,-1,sizeof(dp));
        dp[0][0]=0;
        for(i=1;i<=l[0];++i)
            for(j=k-1;j>=0;--j)
                for(r=0;r<p;++r)
                    if(dp[j][r]>=0)
                        dp[j+1][(r+l[i])%p]=max(dp[j+1][(r+l[i])%p],dp[j][r]+l[i]);
        g<<dp[k][0]<<"\n";
    }
}