#include <iostream>
#include <vector>

#define PMax 22
#define KMax 5

using namespace std;

vector <int> Hash[PMax][PMax];
int N, Stack[KMax+2], CurrentP, S;
bool V[PMax][PMax][KMax+2];

void Insert (int X, int P)
{
    int Key=X%P;
    if (Hash[P][Key].size ()<KMax)
    {
        Hash[P][Key].push_back (X);
    }
    if (Hash[P][Key].size ()==KMax)
    {
        int iMin=0, XMin=Hash[P][Key][0];
        for (unsigned i=1; i<Hash[P][Key].size (); ++i)
        {
            if (Hash[P][Key][i]<XMin)
            {
                iMin=i;
                XMin=Hash[P][Key][i];
            }
        }
        if (XMin<X)
        {
            Hash[P][Key][iMin]=X;
        }
    }
}

int DetMax (int P, int Key)
{
    int XMax=-1, iMax=-1;
    for (unsigned i=0; i<Hash[P][Key].size (); ++i)
    {
        if (Hash[P][Key][i]>XMax and !V[P][Key][i])
        {
            iMax=i;
            XMax=Hash[P][Key][i];
        }
    }
    if (XMax!=-1)
    {
        V[P][Key][iMax]=true;
    }
    return XMax;
}

void BuildSolution (int P, int K)
{
    int CurrentS=0;
    for (int i=1; i<=K; ++i)
    {
        int X=DetMax (P, Stack[i]);
        if (X==-1)
        {
            return;
        }
        else
        {
            CurrentS+=X;
        }
    }
    if (CurrentS>S)
    {
        S=CurrentS;
    }
}

void Back (int k, int P, int K)
{
    if (k==K)
    {
        Stack[k]=(P-CurrentP%P)%P;
        memset (V, false, sizeof (V));
        BuildSolution (P, K);
    }
    else
    {
        for (int i=Stack[k-1]; i<P; ++i)
        {
            CurrentP+=i;
            Stack[k]=i;
            Back (k+1, P, K);
            CurrentP-=i;
            Stack[k]=0;
        }
    }
}

int main()
{
    freopen ("tricouri.in", "r", stdin);
    freopen ("tricouri.out", "w", stdout);
    int M;
    scanf ("%d %d", &N, &M);
    for (int i=1; i<=N; ++i)
    {
        int X;
        scanf ("%d", &X);
        for (int P=2; P<=20; ++P)
        {
            Insert (X, P);
        }
    }
    for (; M>0; --M)
    {
        int K, P;
        scanf ("%d %d", &K, &P);
        S=-1;
        Back (1, P, K);
        printf ("%d\n", S);
    }
    return 0;
}