#include <stdio.h>

int nr[21][20][7],max,suma,p,k,n,m,rest;

void back(int t,int last)
{
   if (t==k)
     {
        int i=(4*p-rest)%p;
        int val=suma+nr[p][i][nr[p][i][0]];
        if (val>max) max=val;
     }
   else for (int i=last;i<p;i++)
           if (nr[p][i][nr[p][i][0]]>0)
           {
               suma+=nr[p][i][nr[p][i][0]];
               nr[p][i][0]++;
               rest+=i;
               back(t+1,i);
               nr[p][i][0]--;
               suma-=nr[p][i][nr[p][i][0]];
               rest-=i;
           }
}

int main()
{
   freopen("tricouri.in","r",stdin);
   freopen("tricouri.out","w",stdout);
   scanf("%d %d",&n,&m);
   for (int i=2;i<=20;i++)
      for (int j=0;j<i;j++)
          for (int k=0;k<=4;k++) nr[i][j][k]=-6000000;
   for (int i=0;i<n;i++)
      {
         int x;
         scanf("%d",&x);
         for (int k=2;k<=20;k++)
            {
               int r=x%k,t=5;
               while (t>=1 && nr[k][r][t]<x) nr[k][r][t+1]=nr[k][r][t],t--;
               nr[k][r][t+1]=x;
            }
      }

   for (int test=0;test<m;test++)
      {
         scanf("%d %d",&k,&p);
         max=-1; suma=0; rest=0;
         for (int i=0;i<p;i++) nr[p][i][0]=1;
         back(1,0);
         printf("%d\n",max);
      }

   fclose(stdout);
   return 0;
}