#include <bits/stdc++.h>
using namespace std;
ifstream f("tricouri.in");
ofstream g("tricouri.out");
const int nMax = 300003;
int a[nMax], dp[3][7][20];
inline void Builddp(const int n, const int k,const int p) {
    int lin = 1;
    memset(dp,-1,sizeof(dp));
    dp[0][0][0] = 0;
    dp[1][0][0] = 0;
    for(int i = 1; i <= n; i++, lin = 1 - lin) {
        int val = a[i] % p;
        for(int j = 1; j <= k; j++) {
            for(int rest = 0; rest < p; rest++) {
                dp[lin][j][rest] = dp[1 - lin][j][rest];
                int r = rest - val;
                if(r < 0) {
                    r += p;
                }
                if(dp[1 - lin][j - 1][r] != -1)
                    dp[lin][j][rest] = max(dp[lin][j][rest], dp[1 - lin][j - 1][r] + a[i]);
            }
        }
    }
}
int main()
{
    int n , m, k, p;
    f >> n >> m;
    for(int i = 1; i <= n; i++) {
        f >> a[i];
    }
    while(m--) {
        f >> k >> p;
        Builddp(n,k,p);
        if(dp[n&1][k][0]) {
            g<< dp[n&1][k][0] << "\n";
        }
        else {
            g<<"-1\n";
        }
    }
    return 0;
}