#include<fstream>
#include<algorithm>
#define PMAX 21
#define KMAX 6
#define NMAX 300010

using namespace std;

ifstream f("tricouri.in");
ofstream g("tricouri.out");

int n, m, val[PMAX][PMAX][KMAX], a[NMAX], sum[KMAX], ind[PMAX];

int i, p, z, k, mx, T;

void Back(int h)
{
    int i;
    if (h==k+1){if(sum[k]>mx && sum[k]%p==0) mx=sum[k];}
    else
    {
        for (i=0; i<p; ++i)
            if (ind[i]<=val[p][i][0])
            {
                sum[h]=sum[h-1]+val[p][i][ind[i]++];
                Back(h+1);
                sum[h]=0; --ind[i];
            }
    }
}

int main()
{
    f>>n>>m;

    for (i=1; i<=n; ++i) f>>a[i];

    sort(a+1, a+n+1);

    for (i=n; i>0; --i)
    {
        for (p=2; p<=20; ++p)
        {
            z=a[i]%p;

            if (val[p][z][0]<5)
                val[p][z][++val[p][z][0]]=a[i];
        }
    }

    for (T=1; T<=m; ++T)
    {
        f>>k>>p;

        for (i=0; i<p; ++i) ind[i]=1;

        mx=-1;

        Back(1);

        g<<mx<<"\n";
    }

    f.close();
    g.close();
    return 0;
}