#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 300000;
int n,m;
int a[N];
int k,p;
int s,sm;

void back ( int lvl, int prev ) {
    for (int i = prev + 1; i < n; ++i) {
        s += a[i];
        if (lvl == k-1) {
            if (s > sm && s % p == 0) {
                sm = s;
            }
        } else {
            back(lvl+1,i);
        }
        s -=a[i];
    }
}

int main() {
    freopen("tricouri.in","r",stdin);
    freopen("tricouri.out","w",stdout);
    int m;
    scanf("%d %d",&n,&m);
    for (int i = 0; i<n; i++) {
        scanf("%d",&a[i]);
    }
    sort(a,a+n);
    for (; m>0; --m) {
        scanf("%d %d",&k,&p);
        sm = -1; s = 0;
        back(0,-1);
        printf("%d\n",sm);
    }
    return 0;
}