#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream f ("tricouri.in");
ofstream g ("tricouri.out");

const int NMAX = 300000 + 1, PMAX = 20, KMAX = 5, MMAX = 100;

int n, m;
int buline[NMAX];
vector <int> v, resturi[PMAX + 1][PMAX + 1];
int sol[KMAX][PMAX];

void citeste() {
    f >> n >> m;
    for (int i = 1; i <= n; i++) f >> buline[i];
}

inline bool conditie(int a, int b) {
    return a > b;
}

void initializeaza() {
    int rest;
    for (int i = 1; i <= n; i++)
        for (int j = 2; j <= PMAX; j++) {
            rest = buline[i] % j;
            if (resturi[j][rest].size() < KMAX) resturi[j][rest].push_back(buline[i]);
        }
}

void reinitializeaza(int k, int p) {
    for (int i = 0; i <= k; i++)
        for (int j = 0; j <= p; j++)
            sol[i][j] = 0;
    v.clear();
}


void rezolva() {
    int k, p, l;
    while(m--) {
        f >> k >> p;
        reinitializeaza(k, p);
        for (int i = 0; i <= p; i++) {
            l = resturi[p][i].size();
            for (int j = 0; j < l; j++) v.push_back(resturi[p][i][j]);
        }
        int lim = v.size();
        for (int i = 0; i < lim; i++) {
            for (int j = k - 1; j >= 0; j--)
                for (int l = 0; l < p; l++)
                    if (sol[j][l] != 0)
                        sol[j + 1][(l + v[i]) % p] = max(sol[j][l] + v[i], sol[j + 1][(l + v[i]) % p]);
            if (sol[1][v[i] % p] == 0) sol[1][v[i] % p] = v[i];
        }

        if (sol[k][0] == 0) sol[k][0] = -1;
        g << sol[k][0] << '\n';
    }
}



int main() {
    citeste();
    sort(buline + 1, buline + n + 1, conditie);
    initializeaza();
    rezolva();
}