#include <algorithm>
#include <set>
using namespace std;

#define INF 0x3f3f3f3f
#define DIM 25
#define LIM 20
#define MAX 5

int best[DIM][DIM],dp1[DIM][DIM],dp2[DIM][DIM];
int v[DIM*DIM];
int n,m,lg;

struct cmp
{
    bool operator () (const int &a,const int &b) const
    {
        return a>b;
    }
}; set <int,cmp> g[DIM][DIM];

void read ()
{
    set <int> :: iterator it;
    int i,j,x;

    scanf ("%d%d",&n,&m);
    for (i=1; i<=n; ++i)
    {
        scanf ("%d",&x);
        for (j=2; j<=LIM; ++j)
            if (g[j][x%j].size ()<MAX)
                g[j][x%j].insert (x);
            else
            {
                it=g[j][x%j].end ();
                if (*(--it)<x)
                {
                    g[j][x%j].erase (it);
                    g[j][x%j].insert (x);
                }
            }
    }
}

void solve ()
{
    set <int> :: iterator it;
    int i,j,k,p;

    for (p=2; p<=LIM; ++p)
    {
        for (lg=i=0; i<p; ++i)
            for (it=g[p][i].begin (); it!=g[p][i].end (); ++it)
                v[++lg]=*it;
        memset (dp1,0,sizeof (dp1));
        dp1[1][v[1]%p]=v[1];
        for (i=2; i<=lg; ++i)
        {
            memcpy (dp2,dp1,sizeof(dp1));
            for (j=1; j<=MAX; ++j)
                for (k=0; k<p; ++k)
                    if (dp1[j][k])
                        dp2[j+1][(k+v[i])%p]=max (dp2[j+1][(k+v[i])%p],dp1[j][k]+v[i]);
            if (v[i]>dp2[1][v[i]%p])
                dp2[1][v[i]%p]=v[i];
            memcpy(dp1,dp2,sizeof(dp2));
        }
        for (i=1; i<=MAX; ++i)
            if (dp1[i][0]>0)
                best[p][i]=dp1[i][0];
            else
                best[p][i]=-1;
    }
    for (i=1; i<=m; ++i)
    {
        scanf ("%d%d",&k,&p);
        printf ("%d\n",best[p][k]);
    }
}

int main ()
{
    freopen ("tricouri.in","r",stdin);
    freopen ("tricouri.out","w",stdout);

    read ();
    solve ();

    return 0;
}