#include <stdio.h>

#define Inf 0x3f3f3f3f

int st[300100],v[300100],i,j,max,sum,P,N,M,m,k,as,es;

void succesor(int st[], int k, int &as)
{
    if (st[k]<N)
    {
        st[k]++;
        as=1;
    }
    else
    as=0;
}

void valid(int st[], int k, int &es)
{
    es=1;
    sum=v[st[k]];
    for (i=1;i<k;++i)
         if (st[k]==st[i])
             {
                  es=0;
                  break;
             }
             else
             sum+=v[st[i]];
}

void tipar()
{
    if (sum>max && sum%P==0)
         max=sum;
}


int main()
{
    freopen("tricouri.in","r",stdin);
        
    scanf("%d %d",&N,&M);
    for (i=1;i<=N;++i)
          scanf("%d", &v[i]);
    freopen("tricouri.out","w",stdout);
    while(M--)
    {
        scanf("%d %d", &m,&P);
        max=-Inf;
        k=1;
        st[k]=0;
        while(k>0)
        {
            do
            {
              succesor(st,k,as);
              if (as)
                   valid(st,k,es);
            }
            while(!((as && es) || !(as)));
        if (as)
            if (k==m)
                tipar();
                else
                st[++k]=0;
            else
            --k;
        }
       if (max==-Inf)
           printf("-1\n");
           else
           printf("%d\n", max);  
    }    
    return 0;
}