#include <cstdio>
#include<algorithm>
#define MAXN 300000
#define MAXP 20
#define MAXK 5
using namespace std;
int n1, v[MAXN+1], d[MAXP*MAXK+1][MAXK+1][MAXP], e[MAXP*MAXK+1][MAXK+1][MAXP], n, m, rasp[MAXP+1][MAXK+1], a[MAXP*MAXK+1], dq[MAXP+1];
bool descr(const int a, const int b)
{
    return (a>b);
}
void init(int p)
{
    int i, j, t;
    n1=0;
    for(i=0;i<MAXP;i++)
        dq[i]=0;
    for(i=1;i<=n;i++)
        if(dq[v[i]%p]<MAXK)
        {
            a[++n1]=v[i];
            dq[v[i]%p]++;
        }
    for(i=0;i<=n1;i++)
        for(j=0;j<=MAXK;j++)
            for(t=0;t<MAXP;t++)
                d[i][j][t]=e[i][j][t]=0;
}
inline int maxim(int a, int b)
{
    if(a>b)
        return a;
    return b;
}
int main()
{
    freopen("tricouri.in", "r", stdin);
    freopen("tricouri.out", "w", stdout);
    int p, k, i, t, j;
    scanf("%d%d", &n, &m);
    for(i=1;i<=n;i++)
        scanf("%d", &v[i]);
    sort(v+1, v+n+1, descr);
    // d[i][j][t] -> suma maxima pe care o pot obtine din primele i elemente, alegand j elemente, care sa dea restul t la imp cu p
    for(p=2;p<=MAXP;p++)
    {
        init(p);
        for(j=0;j<=n1;j++)
            e[j][0][0]=1;
        for(i=1;i<=n1;i++)
        {
            for(j=1;j<=MAXK;j++)
            {
                for(t=0;t<p;t++)
                {
                    if(e[i-1][j-1][t])
                    {
                        if(d[i-1][j-1][t]+a[i]>d[i][j][(t+a[i])%p])
                            d[i][j][(t+a[i])%p]=d[i-1][j-1][t]+a[i];
                        e[i][j][(t+a[i])%p]=1;
                    }
                    d[i][j][t]=maxim(d[i][j][t], d[i-1][j][t]);
                    e[i][j][t]=maxim(e[i][j][t], e[i-1][j][t]);
                }
            }
        }
        for(i=1;i<=MAXK;i++)
            rasp[p][i]=d[n1][i][0];
    }
    for(i=1;i<=m;i++)
    {
        scanf("%d%d", &k, &p);
        if(rasp[p][k]==0)
            printf("-1\n");
        else printf("%d\n", rasp[p][k]);
    }
    return 0;
}