#include <stdio.h>
#include <algorithm>

using namespace std;

#define maxl 6
#define mod 21
#define maxn 300010

int n,m;
int a[maxn];
int b[maxl][mod][mod],l[mod][mod];
int c[maxl][mod][mod],d[maxl][mod][mod];

int main()
{
    freopen("tricouri.in","r",stdin);
    freopen("tricouri.out","w",stdout);
    
    scanf("%d %d",&n,&m);
    
    int i,j,k,x,y;
    
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    
	sort(a+1,a+n+1);
    
    for (i=n;i>0;i--)
      for (j=2;j<mod;j++)
        if (l[j][a[i]%j]<maxl-1) b[++l[j][a[i]%j]][j][a[i]%j]=a[i];
        
    for (i=0;i<maxl;i++)
      for (j=2;j<mod;j++)
        for (k=0;k<j;k++) c[i][j][k]=-1;
        
    for (j=2;j<mod;j++) c[0][j][0]=0;

    for (j=2;j<mod;j++)
      for (k=0;k<j;k++)
        for (i=1;i<=l[j][k];i++)        
        {
            for (x=0;x<maxl;x++)
			  for (y=0;y<j;y++) d[x][j][y]=c[x][j][y];
              
            for (x=0;x<maxl-1;x++)
              for (y=0;y<j;y++) 
                if ((d[x][j][y]!=-1) && (d[x][j][y]+b[i][j][k]>c[x+1][j][(y+b[i][j][k])%j]))
                  c[x+1][j][(y+b[i][j][k])%j]=d[x][j][y]+b[i][j][k];
        }  
        
    for (i=1;i<=m;i++)
    {
        scanf("%d %d",&x,&y);
        printf("%d\n",c[x][y][0]);
    }
        
    return 0;
}