#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];
bitset<PMAX + 5>viz;
vector<int>get_divisors(int n){
    vector<int>div;
    for (int i = 1; i * i <= n; i++){
        if (n % i == 0){
            div.push_back(i);
            if (i * i != n)
                div.push_back(n / i);
        }
    }
    return div;
}
void solve_query(int k, int p){
    int dp[KMAX + 5][PMAX + 5]; /// dp[i][j] - suma maxima formata din i 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]);
             }
    }
    auto morb = get_divisors(p);
    for (auto div:morb){
        viz[div] = true;
         if (!v[div].empty()){
            for (auto it:v[div]){
                for (int i = 0; i < p; i += div)
                    ans[it.second] = max(ans[it.second], dp[it.first][i]);
            }
        }
    }
}
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}), ans[i] = INT_MIN;
    for (int i = 20; i >= 1; i--){
        if (!viz[i])
            solve_query(min(20, n), i);
    }
    for (int i = 1; i <= q; ++i)
        fout << ans[i] << "\n";
    return 0;
}