#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];
int smin[27];

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);    
        }    
    }
}

int main() {
	freopen("tricouri.in", "r", stdin);
	freopen("tricouri.out", "w", stdout);
	
	scanf("%d%d ", &n, &m);
	
	ind = 0;
	for (i = 1; i <= n; i++) {
	   scanf("%d", &v[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]++;
		   }
    	   else {
	       		pmin = 0; 
    	        for (k = 1; k < sz[j][rr]; k++)
        	    	if (v[x[j][rr][k]] < v[x[j][rr][pmin]])
            	    	pmin = k;
	            if (v[i] > v[x[j][rr][pmin]])
    	        	x[j][rr][pmin] = i; 
           }
	   }
    }

//	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;
}