#include <cstdio>
#include <math.h>
#include <algorithm>
 
using namespace std;
#define llu long long unsigned
#define ll long long
#define pb push_back
#define mp make_pair
 
//string problemName = "tricouri";
//string inFile = problemName+".in";
//string outFile = problemName+".out";
//ifstream fin(inFile.c_str());
//ofstream fout(outFile.c_str());
 
int dp[25][25][25], v[300005], ax[105], nr[25];
//dp[i][j][k] = S = suma maxima formata din i nr care are S%j == k
 
int main(){
    int n,q,i,j,x,l,cnt,k,p;
    freopen("tricouri.in", "r", stdin);
    freopen("tricouri.out", "w", stdout);
    scanf("%d %d",&n,&q);
    for(i = 1;i <= n;i++){
        scanf("%d",&v[i]);
    }
    sort(v+1, v+n+1);
    for(i = 0;i <= 5;i++){
        for(j = 2;j <= 20;j++){
            for(k = 1;k < 20;k++){
                dp[i][j][k] = -1e9;
            }
        }
    }
    for(j = 2;j <= 20;j++){
        l = j;
        cnt = 0;
        for(i = 0;i < 20;i++){
            nr[i] = 0;
        }
        for(i = n;i >= 1;i--){
            x = v[i];
            if(nr[x%j] < 5){
                nr[x%j]++;
                ax[++cnt] = x;
                if(nr[x%j] == 5){
                    l--;
                }
            }
            if(l == 0){
                break;
            }
        }
        for(i = 1;i <= cnt;i++){
            for(k = 1;k <= 5;k++){
                for(l = 0;l < 20;l++){
                    x = l-ax[i]%j;
                    if(x < 0){
                        x += j;
                    }
                    dp[k][j][l] = max(dp[k][j][l], dp[k-1][j][x]+ax[i]);
                }
            }
        }
    }
    for(i = 1;i <= q;i++){
        scanf("%d %d",&k,&p);
        printf("%d\n", (dp[k][p][0] > 0 ? dp[k][p][0] : -1));
    }
    return 0;
}