#include <bits/stdc++.h>
const int NMAX = 3e5;
const int KMAX = 5;
const int PMAX = 20;
const int MMAX = 1e2;
using namespace std;
using pii = pair<int, int>;
ifstream fin ("tricouri.in");
ofstream fout ("tricouri.out");
int arr[NMAX + 5], ans[MMAX + 5], n, q, k, p;
vector<pii>v[PMAX + 5];
void solve_query(int k, int p){
    int dp[KMAX + 5][PMAX + 5]; /// dp[i][j] - suma maxima formata din k tricouri cu restul j
    fin >> k >> p;
    for (int i = 0; i <= k; i++)
        for (int j = 0; j <= p; j++)
            dp[i][j] = -1;
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++){
         for (int j = min(i, k); j >= 1; j--)
             for (int rest = p - 1; rest >= 0; rest--){
                  int chomp = (rest - arr[i] % p + p) % p;
                  if (dp[j - 1][chomp] != -1)
                     dp[j][rest] = max(dp[j][rest], dp[j - 1][chomp] + arr[i]);
             }
    }
    for (auto it:v[p])
        ans[it.second] = dp[it.first][0];
}
signed main(){
    fin >> n >> q;
    for (int i = 1; i <= n; i++)
         fin >> arr[i];
    for (int i = 1, p, k; i <= q; i++)
        fin >> k >> p, v[p].push_back({k, i});
    for (int i = 1; i <= 20; i++){
        if (!v[i].empty()){
            int maxi = INT_MIN;
            for (auto it:v[i])
                maxi = max(maxi, it.first);
            solve_query(maxi, i);
        }
    }
    for (int i = 1; i <= q; i++)
        fout << ans[i] << "\n";
    return 0;
}