#include<fstream>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;
typedef int var;

ifstream fin("tricouri.in");
ofstream fout("tricouri.out");

struct Query {
    var k, i;
    Query(var a, var b) {
        k = a;
        i = b;
    }
};
vector<Query> Queries[21];
var MAXIME[21][6];
var R[6], T[6];
var best;

void check(var k) {

    for(var i=1; i<=k; i++) {
        T[i] = R[i];
    }
    sort(T+1, T+k+1);

    var sum = 0;
    for(var i=1; i<=k; i++) {
        var ind = 0;
        sum += MAXIME[T[i]][0];
        if(MAXIME[T[i]][0] == 0)
            return;
        while(T[i] == T[i+1]) {
            sum += MAXIME[T[i]][++ind];
            if(!MAXIME[T[i]][ind])
                return;
        }
    }

    best = max(best, sum);
}

void getMax(var k, var p, var pas) {
    if(pas == k) {
        var rest = 0;
        for(var i=1; i<k; i++) {
            rest += R[i];
            rest %= p;
        }
        R[k] = (p-rest)%p;
        check(k);
    } else {
        for(var i=R[pas-1]; i<p; i++) {
            R[pas] = i;
            getMax(k, p, pas+1);
        }
    }
}

var SOL[2000];


int main() {

    var n, q, v, val, k, p;

    fin>>n>>q;
    for(var i=1; i<=n; i++) {
        fin>>v;
    }

    for(var i=1; i<=q; i++) {
        fin>>k>>p;
        Queries[p].push_back(Query(k, i));
    }

    for(var p=1; p<=20; p++) {
        if(Queries[p].empty())
            continue;

        fin.seekg(ios_base::beg);
        fin>>n>>q;

        for(var i=0; i<p; i++) {
            memset(MAXIME[i], 0, sizeof(MAXIME[i]));
        }

        for(var i=1; i<=n; i++) {
            fin>>val;
            MAXIME[val%p][5] = val;
            sort(MAXIME[val%p], MAXIME[val%p]+6, [](var a, var b) {
                    return a > b;
                 });
        }

        /*
        for(var i=0; i<p; i++) {
            fout<<i<<" : ";
            for(auto v : MAXIME[i]) {
                fout<<v<<" ";
            }
            fout<<endl;
        }
        */

        for(auto q : Queries[p]) {
            best = -1;
            getMax(q.k, p, 1);
            SOL[q.i] = best;
        }
    }

    for(var i=1; i<=q; i++) {
        fout<<SOL[i]<<'\n';
    }

    return 0;
}