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

using namespace std;

int i, j, k, p, n, m, pmin;
int v[maxn];
vector<int> x[27][27], mx[27][27];
int s[10];
int sol;

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; 
    int ct[22];
    if (q == k - 1) {
        sum = 0;
        for (i = 1; i <= q; i++)        
            sum = (sum + s[i]) % 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] > 0 && ct[i] <= mx[p][i].size())
                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);    
        }    
    }
}

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]);
	   for (j = 2; j <= 20; j++)
	       if (x[j][v[i] % j].size() < 5)
    	       x[j][v[i] % j].push_back(i);
    	   else {
               pmin = 0;
               for (k = 1; k < x[j][v[i] % j].size(); k++)
                   if (v[x[j][v[i] % j][k]] < v[x[j][v[i] % j][pmin]])
                       pmin = k;
               if (v[i] > v[x[j][v[i] % j][pmin]])
                    v[x[j][v[i] % j][pmin]] = i; 
           }
    }
    
    for (i = 2; i <= 20; i++)
        for (j = 0; j < i; j++)
            sort(x[i][j].begin(), x[i][j].end(), cmp);
            
    for (i = 2; i <= 20; i++)
        for (j = 0; j < i; j++)
            for (k = 0; k < x[i][j].size(); k++) {
                mx[i][j].push_back(v[x[i][j][k]]);
                if (k > 0)
                    mx[i][j][k] += mx[i][j][k - 1];    
            }
    
/*	for (i = 0; i < 5; i++) {
		printf("%d -> ", i);
		for (j = 0; j < x[5][i].size(); j++)
			printf("%d ", x[5][i][j]);
		printf("\n");
	}*/
			
    for (i = 1; i <= m; i++) {
        scanf("%d%d", &k, &p);
        
        sol = -1;
        back(0, k, p);
        printf("%d\n", sol);
           
    }
	
	return 0;
}