#include <stdio.h>
#define MAXP 20
#define MAXK 5
int ma[MAXP + 1][MAXP][MAXK], len[MAXP + 1][MAXP], d[MAXK + 1][MAXP];

int main(){
  FILE *in = fopen("tricouri.in", "r");
  int n, m, i, j, k, l, x, min, p;
  fscanf(in, "%d%d", &n, &m);
  for(i = 0; i < n; i++){
    fscanf(in, "%d", &x);
    for(j = 2; j <= MAXP; j++){
      k = x % j;
      min = x;
      p = -1;
      for(l = 0; l < MAXK; l++){
        if(p == -1 && min > ma[j][k][l]){
          min = ma[j][k][l];
          p = l;
        }
      }
      if(p != -1){
        for(l = MAXK - 1; l > p; l--)
          ma[j][k][l] = ma[j][k][l - 1];
        ma[j][k][l] = x;
        if(len[j][k] < MAXK)
          len[j][k]++;
      }
    }
  }
  for(i = 1; i <= MAXP; i++){
    for(j = 0; j < i; j++){
      for(k = 1; k < MAXK; k++){
        ma[i][j][k] += ma[i][j][k - 1];
      }
    }
  }
  int y, rp;
  FILE *out = fopen("tricouri.out", "w");
  for(i = 0; i < m; i++){
    fscanf(in, "%d%d", &k, &p);
    for(j = 0; j <= k; j++)
      for(l = 0; l < p; l++)
        d[j][l] = -1;
    d[0][0] = 0;
    for(x = 0; x < p; x++){
      for(j = k; j > 0; j--){
        for(l = 0; l < p; l++){
          for(y = 0; y < j && y < len[p][x]; y++){
            rp = (l - x * (y + 1) + p * p) % p;
            if(d[j - y - 1][rp] != -1 && d[j - y - 1][rp] + ma[p][x][y] > d[j][l])
              d[j][l] = d[j - y - 1][rp] + ma[p][x][y];
          }
        }
      }
    }
    fprintf(out, "%d\n", d[k][0]);
  }
  fclose(in);
  fclose(out);
  return 0;
}