#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 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)
                {
                    if(st[0]%h==0)
                    {
                        ok=1;
                        maxi=max(maxi,st[0]);
                    }
                }
                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;
        bk(1);
        if(ok==0)
        {
            fout<<-1<<'\n';
        }
        else fout<<maxi<<'\n';
    }
    return 0;
}