#include <algorithm>
using namespace std;

#define DIM 300005
#define MAX 25
#define LIM 10

int nr[MAX][MAX],bst[LIM][MAX],cst[LIM][MAX];
int v[DIM],aux[MAX*LIM];
int a[MAX][MAX][LIM];
int n,m,p;

void read ()
{
    int i;

    scanf ("%d%d",&n,&m);
    for (i=1; i<=n; ++i)
        scanf ("%d",&v[i]);
}

struct cmp
{
    bool operator () (const int &a,const int &b) const
    {
        return a>b;
    }
};

void solve ()
{
    int i,j,k,l;

    sort (v+1,v+n+1,cmp ());
    for (i=1; i<=n; ++i)
        for (j=2; j<=20; ++j)
            if (nr[j][v[i]%j]<5)
                a[j][v[i]%j][++nr[j][v[i]%j]]=v[i];

    for (i=2; i<=20; ++i)
    {
        for (p=j=0; j<i; ++j)
            for (k=1; k<=nr[i][j]; ++k)
                aux[++p]=a[i][j][k];
        memset (cst,0,sizeof (cst));
        for (j=1; j<=p; ++j)
            for (k=4; k>=0; --k)
                for (l=0; l<i; ++l)
                    if (cst[k][l] || (!k && !l))
                        if (cst[k][l]+aux[j]>cst[k+1][(l+aux[j])%i])
                            cst[k+1][(l+aux[j])%i]=cst[k][l]+aux[j];
        for (j=1; j<=5; ++j)
        {
            bst[j][i]=-1;
            if (cst[j][0])
                bst[j][i]=cst[j][0];
        }
    }
}

void print ()
{
    int i,x,y;

    for (i=1; i<=m; ++i)
    {
        scanf ("%d%d",&x,&y);
        printf ("%d\n",bst[x][y]);
    }
}

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

    read ();
    solve ();
    print ();

    return 0;
}