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

#define DIM 25

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,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<=20; ++j)
        {
            if (g[j][x%j].size ()<5)
                g[j][x%j].insert (x);
            else
            {
                it=g[j][x%j].end ();
                --it;
                if (*it<x)
                {
                    g[j][x%j].erase (it);
                    g[j][x%j].insert (x);
                }
            }
        }
    }
}

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

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

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

    if (step==k)
        check_solve (sumcur);
    else
        for (i=start; i<p; ++i)
        {
            ++f[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=0;
        back (1,0,0);
        if (nrmax)
            printf ("%d\n",nrmax);
        else
            printf ("-1\n");
    }
}

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

    read ();
    solve ();

    return 0;
}