#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <algorithm>
#define FOR(i, a, b) for (i = a; i <= b; i++)
#define maxim(a, b) ((a > b) ? a : b)
#define INF 900000000

using namespace std;

int N, K, P;
int lst[22][22][8], h[22][22], bst;

int st[8], LAST_T[22];

void back(int nivel)
{
     int i, j, rst, sum;
     
     if (nivel == K)
     {
         for (rst = 0, i = 1; i < K; i++)
         {
             rst += st[i];
             if (rst >= P) rst -= P;
         }
         
         if (rst == 0) st[K] = 0; else st[K] = P - rst;

         for (i = 1, sum = 0; i <= K; i++)
         {     
             if (LAST_T[st[i]] == h[P][st[i]])
             {
                for (j = 1; j <= K; j++)
                  LAST_T[st[j]] = 0;
                return ;
             }
             else
                LAST_T[st[i]]++,
                sum += lst[P][st[i]][LAST_T[st[i]]];
         }
                        
         bst = maxim(bst, sum);
         
         for (i = 1; i <= K; i++)
             LAST_T[st[i]] = 0;
             
         return ;
     }
     
     for (i = 0; i < P; i++)
     { st[nivel] = i; back(nivel+1); }
}

int main(void)
{
    int M, i, j, r, x, min, ind;

    freopen("tricouri.in", "r", stdin);
    freopen("tricouri.out", "w", stdout);
    
    scanf("%d %d", &N, &M);
    
    assert(1 <= N && N <= 300000 && 1 <= M && M <= 100);
    
    for (j = 1; j <= N; j++)
    {
        scanf("%d", &x);
        assert(1 <= x && x <= 1000000);
        
        for (P = 2; P <= 20; P++)
        {
            r = x % P;
            
            if (h[P][r] < 5) { lst[P][r][++h[P][r]] = x; continue; }
            
            min = INF; ind = -1;
            for (i = 1; i <= h[P][r]; i++)
                if (min > lst[P][r][i])
                   min = lst[P][r][i], ind = i;
            
            if (min < x)
               lst[P][r][ind] = x;
            
        }
    }
    
    for (P = 2; P <= 20; P++)
        for (r = 0; r < P; r++)
            if (h[P][r] > 1)
            {
               sort(lst[P][r]+1, lst[P][r]+(h[P][r]+1));
               reverse(lst[P][r]+1, lst[P][r]+(h[P][r]+1));
            }
               
     
    for (; M; M--)
    {
        scanf("%d %d", &K, &P);
        
        bst = -1;
        memset(LAST_T, 0, sizeof(LAST_T));
        back(1);
        
        printf("%d\n", bst);
        
        assert(1 <= K && K <= 5 && 2 <= P && P <= 20);
    }
    
    return 0;
}