#include <stdio.h>
#include <string.h>
#define FOR(i, a, b) for (i = a; i <= b; i++)
#define max(a, b) ((a > b) ? a : b)
#define INF 2000000001
#define NMax 10005

int N, v[NMax];
int D[NMax][6][22];

int main(void)
{
    int i, j, r, M, K, P;
    
    freopen("tricouri.in", "r", stdin);
    freopen("tricouri.out", "w", stdout);
    
    
    scanf("%d %d", &N, &M);
    FOR (i, 1, N)
        scanf("%d", &v[i]);
    
    for (; M; M--)
    {
        scanf("%d %d", &K, &P);
        
        memset(D, 0, sizeof(M));

        FOR (i, 0, N)
            FOR (j, 0, K)
                FOR (r, 0, P)
                    D[i][j][r] = -INF;
                
        D[0][0][0] = 0;
        
        FOR (j, 0, K)
            FOR (i, 0, N-1)            
                FOR (r, 0, P-1)      
                {
                    if (D[i][j][r] < 0) continue;
                    
                    D[i+1][j][r] = max(D[i+1][j][r], D[i][j][r]);
                    if (j < K)
                    D[i+1][j+1][(r+v[i+1])%P] = max(D[i+1][j+1][(r+v[i+1])%P],
                                                    D[i][j][r]+v[i+1]);
                }

        
         if (D[N][K][0] < 0)
            printf("-1\n");
         else
             printf("%d\n", D[N][K][0]);
    }
    
    return 0;
}