#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

#define INF 1000000005
#define RMAX 23
#define NMAX 300005

int f[RMAX],numere[RMAX][7];
int v[NMAX],n,m;
int d[RMAX][RMAX][7][RMAX];

int main ()
{
    int i,j,p,k,t,r,newr,a,b,val;

    freopen("tricouri.in","r",stdin);
    freopen("tricouri.out","w",stdout);

    scanf("%d%d",&n,&m);
    for(i = 1; i <= n; i++)
        scanf("%d",&v[i]);
    sort(v + 1, v + n + 1);
    for(i = 2; i <= 20; i++)
    {
        //printf("Pentru i = %d\n",i);
        for(j = 0; j < i; j++)
            f[j] = 0;
        for(j = n; j >= 1; j--)
        {
            val = v[j] % i;
            if(f[val] < 5)
            {
                numere[val][++f[val]] = v[j];
               // printf("I choose you %d la %d\n",v[j],val);
            }
        }
        for(j = 0; j < i; j++)
            for(k = 1; k <= f[j]; k++)
                numere[j][k] += numere[j][k - 1];
        for(p = 0; p <= i; p++)
            for(j = 0; j <= 5; j++)
                for(r = 0; r <= i; r++)
                    d[i][p][j][r] = -INF;
        for(j = 0; j <= 20; j++)
            d[i][j][0][0] = 0;
        for(p = 1; p <= i; p++)
            for(j = 1; j <= 5; j++)
                for(r = 0; r < i; r++)
                    for(t = 0, newr = r; t <= j && t <= f[p - 1]; t++)
                    {
                        d[i][p][j][r] = max(d[i][p][j][r], d[i][p - 1][j - t][newr] + numere[p - 1][t]);
                 //       printf("d[%d][%d][%d][%d] = %d dupa t = %d\n",i,p,j,r,d[i][p][j][r],t);
                        newr -= (p - 1);
                        if(newr < 0)
                            newr += i;
                    }

    }

    for(i = 1; i <= m; i++)
    {
        scanf("%d%d",&a,&b);
        if(d[b][b][a][0] < 0)
            printf("-1\n");
        else
            printf("%d\n",d[b][b][a][0]);
    }

    return 0;
}