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

using namespace std;

int i, j, k, p, n, m, pmin;
int ind;
int v[maxn];
vector<int> x[27][27], mx[27][27];
int s[10];
int sol;
int ct[22];
char sn[1500000];

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]) % 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] > mx[p][i].size())
				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 int get(int &ind) {
	int nr = 0;
	while (sn[ind] < '0' || sn[ind] > '9')
		ind++;	
	while (sn[ind] >= '0' && sn[ind] <= '9') {
		nr = nr * 10 + (sn[ind] - 48);
		ind++;
	}
	while (sn[ind] < '0' || sn[ind] > '9')
		ind++;
	return nr;
}

int main() {
	freopen("tricouri.in", "r", stdin);
	freopen("tricouri.out", "w", stdout);
	
	scanf("%d%d ", &n, &m);
	
	fgets(sn, 1499999, stdin);
	
	ind = 0;
	for (i = 1; i <= n; i++) {
	   v[i] = get(ind);
	   for (j = 2; j <= 20; j++) {
		   int rr = v[i] % j;
	       if (x[j][rr].size() < 5)
    	       x[j][rr].push_back(i);
    	   else {
               pmin = 0; int sz = x[j][rr].size();
               for (k = 1; k < sz; 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; 
           }
	   }
    }
    
    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 = 1; i <= m; i++) {
        scanf("%d%d", &k, &p);
        
        sol = -1;
        back(0, k, p);
        printf("%d\n", sol);
           
    }
	
	return 0;
}