#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <iostream>
#define maxn 300010

using namespace std;

int i, j, k, p, n, m, pmin;
int ind;
int v[maxn];
int x[27][27][6], mx[27][27][6], sz[27][27], sz2[27][27];
int s[10];
int sol;
int ct[22];

bool cmp(int a, int b) {
    if (v[a] > v[b])
        return true;
    return false;   
}

void back(int q, int k, int p) {
    int i, j, sum; 
    if (q == k - 1) {
        sum = 0;
        for (i = 1; i <= q; i++) {
            sum = (sum + s[i]);
			while (sum >= p)
				sum -= p;
		}
        s[k] = p - sum;
        if (s[k] == p)
            s[k] = 0;
            
        memset(ct, 0, sizeof(ct));
        for (i = 1; i <= k; i++)
            ct[s[i]]++;
        
        sum = 0;
        for (i = 0; i < p; i++) {
			if (ct[i] > sz[p][i])
				return;
            if (ct[i] > 0)
                sum += mx[p][i][ct[i] - 1];
		}
                
        if (sum > sol && sum > 0)
            sol = sum;
    }
    else {
        for (i = 0; i < p; i++) {
            s[q + 1] = i;
            back(q + 1, k, p);    
        }    
    }
}

inline bool cmp2(int a, int b) {
	if (a > b)
		return a;
	return 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", &v[i]);
	return 0;
	sort(v + 1, v + n + 1, cmp2);

//	return 0;

	ind = 0;
	for (i = 1; i <= n; i++) 
	   for (j = 2; j <= 20; j++) {
		   int rr = v[i] % j;
	       if (sz[j][rr] < 5) {
    	       x[j][rr][sz[j][rr]] = i;
			   sz[j][rr]++;
		   }     
	   }
 

//	return 0;
    
/*    for (i = 2; i <= 20; i++)
        for (j = 0; j < i; j++)
            sort(x[i][j], x[i][j] + sz[i][j], cmp);*/
            
    for (i = 2; i <= 20; i++)
        for (j = 0; j < i; j++)
            for (k = 0; k < sz[i][j]; k++) {
                mx[i][j][sz2[i][j]] = (v[x[i][j][k]]);
				sz2[i][j]++;
                if (k > 0)
                    mx[i][j][k] += mx[i][j][k - 1];    
            }
    

    for (i = 1; i <= m; i++) {
        scanf("%d%d", &k, &p);
        
        sol = -1;
        back(0, k, p);
        printf("%d\n", sol);
           
    }
	
	return 0;
}