#include<cstdio>
#include<algorithm>
using namespace std;
const int NMAX = 300005;
const int PMAX = 21;
const int KMAX = 6;
int N,M,i,j,k,l,X,Y,A[NMAX],C[PMAX],Cate[PMAX][PMAX],Nr,Rest,From;
int DP[PMAX][KMAX][PMAX],S[PMAX][KMAX*PMAX],R[PMAX][KMAX*PMAX];
bool cmp(int A,int B) {return A>B;}
int main()
{
    freopen("tricouri.in","r",stdin);
    freopen("tricouri.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(i=1;i<=N;i++) scanf("%d",&A[i]);
    sort(A+1,A+N+1,cmp);
    for(i=1;i<=N;i++)
        for(j=2;j<PMAX;j++)
        {
            X=A[i]%j;
            if(Cate[j][X]<5)
            {
                Cate[j][X]++;
                S[j][++C[j]]=A[i];
                R[j][C[j]]=X;
            }
        }
    for(l=2;l<PMAX;l++) // pt fiecare rest facem dinamica
    {
        for(i=0;i<KMAX;i++)
            for(j=0;j<PMAX;j++) DP[l][i][j]=-1;
        DP[l][0][0]=0;
        for(k=1;k<=C[l];k++)
        {
            Nr=S[l][k];
            Rest=R[l][k];
            for(i=5;i;i--)
                for(j=0;j<l;j++)
                {
                    From=j-Rest;
                    if(From<0) From+=l;
                    if(DP[l][i-1][From]!=-1)
                        DP[l][i][j]=max(DP[l][i-1][From]+Nr,DP[l][i][j]);
                }
        }
    }
    for(;M;M--)
    {
        scanf("%d%d",&X,&Y);
        printf("%d\n",DP[Y][X][0]);
    }
    return 0;
}