#include <stdio.h>

#define MAX_N 22

int n, m, nr, r, k, sum, sol;
int A[MAX_N];

void cit() {
    freopen("tricouri.in", "r", stdin);
    freopen("tricouri.out", "w", stdout);
    
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &A[i]);
}

void solve() {
    if (n > 20) for(;;);
    
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &nr, &r);
        
        sol = -1;
        for (int j = 1; j < (1 << n); j++) {
            k = sum = 0;
            for (int t = 0; t < n; t++)
                if (j & (1 << t)) k++;
                
            if (k == nr) {
                for (int t = 0; t < n; t++)
                    if (j & (1 << t)) sum += A[t + 1];
                if (sum % r == 0 && sum > sol) sol = sum;
            }
        } 
        
        printf("%d\n", sol);
    }
}

int main() {

    cit();
    solve();

    return 0;
}