#include <fstream.h>
#include <iostream.h>

long int n,m;
long int v[300001];
struct adat
{
       long int buline;
       short int tricouri;
       long int v[6];
       adat* kov;
};
adat *elso;

void betesz(long int buline,short int tricouri,long int nrt,adat *from)
{
     int i;
     
     adat *p = new adat;
     p -> buline = buline;
     p -> tricouri = tricouri;
     for (i=1;i<tricouri;i++)
         p -> v[i] = from -> v[i];
     p -> v[tricouri] = nrt;
     if (elso == NULL)
     {
        elso = p;
        elso->kov = NULL;
     }
     else if(p->buline <= elso->buline)
     {
          if (p->buline < elso->buline)
          {
             p->kov = elso;
             elso = p;
          }
          else
          {
              if (p->tricouri < elso->tricouri)
              {
                 elso->tricouri=p->tricouri;               
              }
          }
     }
     else
     {
         adat *a;
         a = elso;
         while ((a->kov != NULL) && (a->kov->buline < p->buline))
         {
               a=a->kov;
         }
         if (a->kov == NULL)
         {
            a->kov=p;
            p->kov=NULL;
         }
         else if (a->kov->buline > p->buline)
         {
            p->kov = a->kov;
            a->kov = p;
         }
         else
         {
             if (a->kov->tricouri > p->tricouri)
             {
                a->kov->tricouri = p->tricouri;
             }
         }
     }
}

void torol()
{
     adat *p = elso;
     while (p != NULL)
     {
           p=elso->kov;
           delete elso;
           elso = p;        
     }
}

long int keres(int k,int p)
{
     long int i,j,max;
     bool control;
     
     for (i=1;i<=n;i++)
     {
         betesz(v[i],1,i,NULL);               
     }
     
     adat *a = elso;
     
     while (a != NULL)
     {
           if (a -> tricouri < k)
           {
              for (i=1;i<=n;i++)
              {
                  control=true;
                  for(j=1;j<=a->tricouri;j++)
                  {
                     if(a->v[j]==i) control=false;
                  }
                  if(control) betesz(a->buline+v[i],a->tricouri+1,i,a);
                             
              }            
           }
           a = a -> kov;
     }
     a = elso;
     max = -1;
     
     while (a != NULL)
     {
             if  ((a->buline % p == 0) && (a->tricouri == k))
                 max = a->buline;             
             a = a->kov;
     }
     
     torol();
     
     
     return max;
}

int main()
{  
   long int i;
   short int k,p;
     
   ifstream in; 
   ofstream out;
   in.open("tricouri.in");
   out.open("tricouri.out");
   in >> n >> m;
   
   for (i=1;i<=n;i++)
   {
       in >> v[i];
   }
   
   for (i=1;i<=m;i++)
   {
       in >> k >> p;
       out << keres(k,p) << endl;
   }
   
   in.close();
   out.close();
}