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

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

struct cmp
{
    bool operator () (const int &a,const int &b) const
    {
        return a>b;
    }
}; set <int,cmp> g[DIM][DIM];
int n,m,k,p,sumcur,nrmax;
int f[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);
                }
            }
    }
}

inline void check_solve ()
{
    set <int> :: iterator it;
    int i,j,nrc;

    ++f[(p-sumcur%p)%p];
    for (nrc=0, i=0; i<p; ++i)
        if (f[i]>(int)g[p][i].size ())
        {
            --f[(p-sumcur%p)%p];
            return ;
        }
        else
            for (j=1, it=g[p][i].begin (); j<=f[i] && it!=g[p][i].end (); ++j, ++it)
                nrc+=*it;
    --f[(p-sumcur%p)%p];
    nrmax=max (nrmax,nrc);
}

void back (int step,int start)
{
    int i;

    if (step==k)
        check_solve ();
    else
        for (i=start; i<p; ++i)
        {
            ++f[i];
            sumcur+=i;
            back (step+1,i);
            sumcur-=i;
            --f[i];
        }
}

void solve ()
{
    int i;

    for (i=1; i<=m; ++i)
    {
        scanf ("%d%d",&k,&p);
        nrmax=-INF;
        sumcur=0;
        back (1,0);
        if (nrmax!=-INF)
            printf ("%d\n",nrmax);
        else
            printf ("-1\n");
    }
}

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

    read ();
    solve ();

    return 0;
}