#include <bits/stdc++.h>
using namespace std;
ifstream fin("tricouri.in");
ofstream fout("tricouri.out");
int n, m, k, h, maxi, a[22][22][7], st[7];
bool ok, d[22][7];
void solutie()
{
    int q=1;
    while(d[(h-st[0]%h)%h][q]==1) q++;
    if(a[h][(h-st[0]%h)%h][q]) maxi=max(maxi,st[0]+a[h][(h-st[0]%h)%h][q]), ok=1;
}
void bk(int nivel)
{
    for(int i=0; i<=h-1; i++)
        for(int j=1; j<=5; j++)
            if(!d[i][j] && a[h][i][j])
            {
                d[i][j]=1;
                st[nivel]=a[h][i][j];
                st[0]+=st[nivel];
                if(nivel==k-1) solutie();
                else bk(nivel+1);
                st[0]-=st[nivel];
                d[i][j]=0;
            }
}
int main()
{
    int i, j, p, q, x;
    fin>>n>>m;
    for(i=1; i<=n; i++)
    {
        fin>>x;
        for(j=2; j<=20; j++)
        {
            p=5;
            while(x>a[j][x%j][p] && p>=1) p--;
            for(q=5; q>=p+2; q--) a[j][x%j][q]=a[j][x%j][q-1];
            a[j][x%j][p+1]=x;
        }
    }
    for(i=1; i<=m; i++)
    {
        maxi=INT_MIN;
        ok=0;
        fin>>k>>h;
        if(k==1)
        {
            if(a[h][0][1]) fout<<a[h][0][1]<<'\n';
            else fout<<-1<<'\n';
        }
        else
        {
            bk(1);
            if(ok==0)
            {
                fout<<-1<<'\n';
            }
            else fout<<maxi<<'\n';
        }
    }
    return 0;
}